算法-堆-求整型中位数

灰太狼 2023-07-25 09:27 20阅读 0赞

# 算法-堆-求整型中位数 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

## 1.2 题目描述 ##

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

\[2,3,4\] 的中位数是 3

\[2,3\] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。  
double findMedian() - 返回目前所有元素的中位数。  
示例 1：

输入：  
\[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”\]  
\[\[\],\[1\],\[2\],\[\],\[3\],\[\]\]  
输出：\[null,null,null,1.50000,null,2.00000\]  
示例 2：

输入：  
\[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”\]  
\[\[\],\[2\],\[\],\[3\],\[\]\]  
输出：\[null,null,2.00000,null,2.50000\]

限制：

最多会对 addNum、findMedia进行 50000 次调用。

# 2 题解 #

## 2.1 排序法 ##

### 2.1.1 解题思路 ###

将数据放到数组，需要找到中位数的时候排序即可。

### 2.1.2 时间复杂度 ###

*  插入  
    O(1)
 *  寻找中位数  
    采用堆排序О(nlogn)，然后从排序后的数组找出中位数即可。

### 2.1.3 空间复杂度 ###

O(n)

*  构建大小为n的数组

### 2.1.4 优化-二分查找插入 ###

每次插入时先用二分查找找到合适位置并插入元素，也就是说每次插入前后都是排好序状态，这样中位数就很好找出了。

*  时间复杂度  
    O(logn)查找+O(n)插入后移动元素
 *  空间复杂度  
    O(n)

## 2.2 双堆-由优先级队列实现 ##

### 2.2.1 解题思路 ###

1.  采用两个优先级队列分别模仿两个堆，一个堆为大根堆，另一个为小根堆。
2.  每次交替向其中一个堆放元素，并取出堆顶元素放入另一个堆内。
3.  最终形成的两个堆内，大根堆的堆顶为靠近中位数的较小值；小根堆的堆顶为中位数或靠近中位数的较大值

### 2.2.2 代码 ###

class MedianFinder { 
        private PriorityQueue<Integer> minQueue;
        private PriorityQueue<Integer> maxQueue;
        int flip = 0;
    
        /** initialize your data structure here. */
        public MedianFinder() { 
            minQueue = new PriorityQueue();
            maxQueue = new PriorityQueue(Collections.reverseOrder());
        }
        
        public void addNum(int num) { 
            if(flip==0){ 
                minQueue.offer(num);
                maxQueue.offer(minQueue.poll());
            }else{ 
                maxQueue.offer(num);
                minQueue.offer(maxQueue.poll());
            }
            flip = 1-flip;
        }
        
        public double findMedian() { 
            // odd
            if(flip == 1){ 
                return maxQueue.peek();
            }else { 
                return (maxQueue.peek() + minQueue.peek())/2.0f;
            }
        }
    
        public static void main(String[] args) { 
            MedianFinder mf = new MedianFinder();
            mf.addNum(1);
            mf.addNum(2);
            mf.addNum(3);
            System.out.println(mf.findMedian());
        }
    }

### 2.2.3 时间复杂度 ###

O(logn)

*  堆插入和删除需要调整堆，O(logn)，
 *  查找中位数时直接从堆顶找出即可，O(1)

### 2.2.4 空间复杂度 ###

O(n)

## 2.3 自己实现的双堆 ##

### 2.3.1 解题思路 ###

面试时如果直接用`PriorityQueue`面试官可能会不满意，就是考察你写堆你特么给我个封装好的类？

所以这里自己实现。

### 2.3.2 代码 ###

class MedianFinder { 
    
        private List<Integer> max;
        private List<Integer> min;
        private boolean even;
        /** initialize your data structure here. */
        public MedianFinder() { 
            max = new ArrayList<>();
            min = new ArrayList<>();
            even = true;
        }
        
        public void addNum(int num) { 
            if(even){ 
                // 1. 总量偶数时，往大顶堆插入数据 
                max.add(num);
                // 2. 插入数据后，从该节点的父节点开始自底向上一次调整堆
                // 这里i=-1时代表只有一个节点，不用调整堆
                int i = max.size() > 1 ? (max.size() - 2) / 2 : -1;
                while(i >= 0){ 
                    adjustMaxHeap(i, max, max.size());
                    i = i > 0 ?(i-1)/2 : -1;
                }
                // 3. 将大顶堆堆顶节点推出，即交换大顶堆的堆顶节点好堆尾节点并重新从堆顶自顶向下调整该堆
                int tmp = max.get(0);
                max.set(0,max.get(max.size()-1));
                max.remove(max.size()-1);
                adjustMaxHeap(0, max, max.size());
                // 4. 将大顶堆中最大的元素加入小顶堆
                min.add(tmp);
                // 5. 插入数据后，从该节点的父节点开始自底向上一次调整堆
                i = min.size() > 1 ? (min.size() - 2) / 2 : -1;
                while(i >= 0){ 
                    adjustMinHeap(i, min, min.size());
                    i = i > 0 ?(i-1)/2 : -1;
                }
                // 6. 这样操作一波后，即将元素先加入大顶堆调整后，将最大的元素加入小顶堆并调整
                // 此时大顶堆存放最小的那部分元素，小顶堆存放最大的那部分元素
            }else{ 
                min.add(num);
                int i = min.size() > 1 ? (min.size() - 2) / 2 : -1;
                while(i >= 0){ 
                    adjustMinHeap(i, min, min.size());
                    i = i > 0 ?(i-1)/2 : -1;
                }
                int tmp = min.get(0);
                min.set(0,min.get(min.size()-1));
                min.remove(min.size()-1);
                adjustMinHeap(0, min, min.size());
                max.add(tmp);
                i = max.size() > 1 ? (max.size() - 2) / 2 : -1;
                while(i >= 0){ 
                    adjustMaxHeap(i, max, max.size());
                    i = i > 0 ?(i-1)/2 : -1;
                }
            }
            even = !even;
        }
        
        public double findMedian() { 
            if(even){ 
                // 1. 总量为偶数时，取大顶堆中最大的和小顶堆中最小的之和的二分之一就是中位数
                // 注意这里要除以2.0d，转换为浮点型小数
                return max.size() == 0 ? 0d : ((max.get(0) + min.get(0)) / 2.0d);
            }else{ 
                // 2. 总量为奇数时，返回小顶堆中的堆顶元素就是中位数
                return min.get(0);
            }
        }
    
        /** * 自顶向下调整大顶堆 */
        public void adjustMaxHeap(int index, List<Integer> nums, int k){ 
            if(nums.size() < 1){ 
                return;
            }
            int tmp = nums.get(index);
            for(int i = 2 * index+1; i < k; i = 2 * i+1){ 
                if(i+1 < k){ 
                    i = nums.get(i) > nums.get(i+1) ? i : i+1;
                }
                if(tmp < nums.get(i)){ 
                    nums.set(index,nums.get(i));
                    index = i;
                }else{ 
                    break;
                }
            }
            nums.set(index,tmp);
        }
    
        /** * 自顶向下调整小顶堆 */
        public void adjustMinHeap(int index, List<Integer> nums, int k){ 
            if(nums.size() < 1){ 
                return;
            }
            int tmp = nums.get(index);
            for(int i = 2 * index+1; i < k; i = 2 * i+1){ 
                if(i+1 < k){ 
                    i = nums.get(i) < nums.get(i+1) ? i : i+1;
                }
                if(tmp > nums.get(i)){ 
                    nums.set(index,nums.get(i));
                    index = i;
                }else{ 
                    break;
                }
            }
            nums.set(index,tmp);
        }
    }

## 2.3 自己实现的双堆-优化版 ##

### 2.3.1 解题思路 ###

上一个版本调整堆全部用的自顶向下的方法，其实插入元素时应该用自底向上调整。

### 2.3.2 代码 ###

class MedianFinder { 
    
        private List<Integer> max;
        private List<Integer> min;
        private boolean even;
        /** initialize your data structure here. */
        public MedianFinder() { 
            max = new ArrayList<>();
            min = new ArrayList<>();
            even = true;
        }
        
        public void addNum(int num) { 
            if(even){ 
                // 1. 总量偶数时，往大顶堆插入数据 
                max.add(num);
                // 2. 插入数据后，从该节点开始自底向上调整一次大顶堆
                adjustMaxHeapUp(max.size() - 1, max, max.size());
                // 3. 将大顶堆堆顶节点推出，即交换大顶堆的堆顶节点好堆尾节点并重新从堆顶自顶向下调整该堆
                int tmp = max.get(0);
                max.set(0,max.get(max.size()-1));
                max.remove(max.size()-1);
                adjustMaxHeap(0, max, max.size());
                // 4. 将大顶堆中最大的元素加入小顶堆
                min.add(tmp);
                // 5. 插入数据后，从该节点开始自底向上调整一次小顶堆
                adjustMinHeapUp(min.size() - 1, min, min.size());
                // 6. 这样操作一波后，即将元素先加入大顶堆调整后，将最大的元素加入小顶堆并调整
                // 此时大顶堆存放最小的那部分元素，小顶堆存放最大的那部分元素
            }else{ 
                min.add(num);
                adjustMinHeapUp(min.size() - 1, min, min.size());
                int tmp = min.get(0);
                min.set(0,min.get(min.size()-1));
                min.remove(min.size()-1);
                adjustMinHeap(0, min, min.size());
                max.add(tmp);
                adjustMaxHeapUp(max.size() - 1, max, max.size());
            }
            even = !even;
        }
        
        public double findMedian() { 
            if(even){ 
                // 1. 总量为偶数时，取大顶堆中最大的和小顶堆中最小的之和的二分之一就是中位数
                // 注意这里要除以2.0d，转换为浮点型小数
                return max.size() == 0 ? 0d : ((max.get(0) + min.get(0)) / 2.0d);
            }else{ 
                // 2. 总量为奇数时，返回小顶堆中的堆顶元素就是中位数
                return min.get(0);
            }
        }
    
        /** * 自顶向下调整大顶堆 */
        public void adjustMaxHeap(int index, List<Integer> nums, int k){ 
            if(nums.size() <= 1){ 
                return;
            }
            int tmp = nums.get(index);
            for(int i = 2 * index+1; i < k; i = 2 * i+1){ 
                if(i+1 < k){ 
                    i = nums.get(i) > nums.get(i+1) ? i : i+1;
                }
                if(tmp < nums.get(i)){ 
                    nums.set(index,nums.get(i));
                    index = i;
                }else{ 
                    break;
                }
            }
            nums.set(index,tmp);
        }
    
        /** * 自底向上调整大顶堆 */
        public void adjustMaxHeapUp(int index, List<Integer> nums, int k){ 
            if(nums.size() <= 1){ 
                return;
            }
            int tmp = nums.get(index);
            int parent;
            while(index > 0){ 
                parent = (index-1)/2;
                if(tmp > nums.get(parent)){ 
                    nums.set(index, nums.get(parent));
                    index = parent;
                }else{ 
                    break;
                }
            }
            nums.set(index,tmp);
        }
    
        /** * 自顶向下调整小顶堆 */
        public void adjustMinHeap(int index, List<Integer> nums, int k){ 
            if(nums.size() < 1){ 
                return;
            }
            int tmp = nums.get(index);
            for(int i = 2 * index+1; i < k; i = 2 * i+1){ 
                if(i+1 < k){ 
                    i = nums.get(i) < nums.get(i+1) ? i : i+1;
                }
                if(tmp > nums.get(i)){ 
                    nums.set(index,nums.get(i));
                    index = i;
                }else{ 
                    break;
                }
            }
            nums.set(index,tmp);
        }
        /** * 自底向上调整小顶堆 */
        public void adjustMinHeapUp(int index, List<Integer> nums, int k){ 
            if(nums.size() <= 1){ 
                return;
            }
            int tmp = nums.get(index);
            int parent;
            while(index > 0){ 
                parent = (index-1)/2;
                if(tmp < nums.get(parent)){ 
                    nums.set(index, nums.get(parent));
                    index = parent;
                }else{ 
                    break;
                }
            }
            nums.set(index,tmp);
        }
    }