【LeetCode】求中位数（数据流、滑动窗口、两个正序数组）

朱雀 2023-01-08 12:30 141阅读 0赞

### 文章目录 ###

*   *   *  数据流中的中位数★★★
         *  滑动窗口中位数★★★
         *  寻找两个正序数组的中位数★★★

--------------------

### 数据流中的中位数★★★ ###

[LeetCode 剑指 Offer 41. 数据流中的中位数][LeetCode _ Offer 41.]

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

例如，

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

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

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

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

【**示例**】

输入：
    ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
    [[],[1],[2],[],[3],[]]
    输出：[null,null,null,1.50000,null,2.00000]

【**解题思路**】**堆**

创建两个堆，其中一个为大根堆，另一个为小根堆。大根堆中保存较小的数，小根堆中保存较大的数。大根堆的队头接小根堆的队头正好形成升序排列的一组数。

每次加入数字x时，先将x加入大根堆，然后大根堆出堆一个数进入小根堆，保持`大根堆数字数目 + 1` 始终`等于小根堆数字数目`或者`大根堆数字数目` 始终`等于小根堆数字数目`

class MedianFinder {
        
        PriorityQueue<Integer> pa;  //大根堆
        PriorityQueue<Integer> pb;  //小根堆
        
        public MedianFinder() {
        
            pa = new PriorityQueue<Integer>((o1, o2) -> Integer.compare(o2, o1));
            pb = new PriorityQueue<Integer>();
        }
        
        public void addNum(int num) {
        
            pa.offer(num);
            pb.offer(pa.poll());
            if(pb.size() - 1 > pa.size()) pa.offer(pb.poll());
        }
        
        public double findMedian() {
        
            return pa.size() == pb.size() ? (double)(pa.peek() + pb.peek()) / 2 : pb.peek();
        }
    }

--------------------

### 滑动窗口中位数★★★ ###

[LeetCode 480. 滑动窗口中位数][LeetCode 480.]

【**题目**】中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

\[2,3,4\]，中位数是 3  
\[2,3\]，中位数是 (2 + 3) / 2 = 2.5  
给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

【**示例**】

给出 *nums* = `[1,3,-1,-3,5,3,6,7]`，以及 *k* = 3。

窗口位置                      中位数
    ---------------               -----
    [1  3  -1] -3  5  3  6  7       1
     1 [3  -1  -3] 5  3  6  7      -1
     1  3 [-1  -3  5] 3  6  7      -1
     1  3  -1 [-3  5  3] 6  7       3
     1  3  -1  -3 [5  3  6] 7       5
     1  3  -1  -3  5 [3  6  7]      6
    
    因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。

【**解题思路**】

**方法一**：思路同上寻找数据流中位数一样，使用两个堆。

需要注意的是，在堆中删除数据时要维护两个堆的大小平衡。

class Solution {
        
        Queue<Integer> lo;   //大根堆
        Queue<Integer> hi;   //小根堆
    
        public double[] medianSlidingWindow(int[] nums, int k) {
        
            lo = new PriorityQueue<Integer>((o1, o2) -> Integer.compare(o2, o1));
            hi = new PriorityQueue<Integer>();
            double[] res = new double[nums.length - k + 1];
            
            for(int i = 0; i < nums.length; i++) {
        
                addNum(nums[i]);
                if(i < k - 1) continue;
                res[i + 1 - k] = getMedium(k);
                delNum(nums[i + 1 - k], k);
            }
    
            return res;
        }
    
        private void addNum(int num) {
        
            lo.offer(num);
            hi.offer(lo.poll());
            if(hi.size() - 1 > lo.size()) lo.offer(hi.poll());
        }
    
        private void delNum(int num, int k) {
        
            if(lo.contains(num)) {
        
                lo.remove(num);
                if(k % 2 == 1) lo.offer(hi.poll());
            }else {
        
                hi.remove(num);
                if(k % 2 == 0) hi.offer(lo.poll());
            }
        }
    
        private double getMedium(int k) {
        
            if(k % 2 == 0) {
        
                return ((double)lo.peek() + hi.peek()) / 2;
            }else {
        
                return (double)hi.peek();
            }
        }
    }

**方法二**：插入排序+二分查找

用插入排序维护一个窗口，每次插入数据时使用二分查找寻找插入位置

class Solution {
        
        public double[] medianSlidingWindow(int[] nums, int k) {
        
            List<Integer> list = new ArrayList<Integer>();
            double[] res = new double[nums.length - k + 1];
    
            for(int i = 0; i < nums.length; i++) {
        
                int pos = binarySearch(list, nums[i]);
                list.add(pos, nums[i]);
                if(list.size() < k) continue;
                if(k % 2 == 0) {
        
                    res[i + 1 - k] = ((double)list.get(k / 2 - 1) + list.get(k / 2)) / 2;
                }else {
        
                    res[i + 1 - k] = (double)list.get(k / 2);
                }
                list.remove((Integer)nums[i + 1 - k]);
            }
            
            return res;
        }
    
        //找到大于它的最小数的下标即为插入下标
        private int binarySearch(List<Integer> list, int val) {
        
            int le = 0, ri = list.size() - 1;
            while(le <= ri) {
        
                int mid = le + (ri - le) / 2;
                if(list.get(mid) <= val) {
        
                    le = mid + 1;
                }else {
        
                    ri = mid - 1;
                }
            }
            return le;
        }
    }

--------------------

### 寻找两个正序数组的中位数★★★ ###

[LeetCode 4. 寻找两个正序数组的中位数][LeetCode 4.]

【**题目**】给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

【**示例**】

输入：nums1 = [1,2], nums2 = [3,4]
    输出：2.50000
    解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

【**解题思路**】

**方法一**：双指针合并

同归并排序中归并的思路一样，但时间复杂度并不符合要求，`时间复杂度：O(m + n)`

class Solution {
        
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
            double res = 0.0;
            int i = 0, j = 0, k = 0;
            int n = nums1.length + nums2.length;
            
            while(k < n) {
        
                double val = 0;
                if(i >= nums1.length) {
        
                    val = nums2[j++];
                }else if(j >= nums2.length) {
        
                    val = nums1[i++];
                }else if(nums1[i] < nums2[j]) {
        
                    val = nums1[i++];
                }else {
        
                    val = nums2[j++];
                }
                k++;
                if(n % 2 == 0) {
        
                    if(k == n / 2) res = (double)val;
                    if(k == n / 2 + 1) {
        
                        res = (res + val) / 2;
                        break;
                    }
                }else {
        
                    if(k == n / 2 + 1) {
        
                        res = (double)val;
                        break;
                    }
                }
            }
            
            return res;
        }
    }

**方法二**：二分查找

`时间复杂度：O(log(m + n))`

解法来自本题力扣热评（Wait想念），如图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

class Solution {
        
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
            int m = nums1.length;
            int n = nums2.length;
            int left = (m + n + 1) / 2;
            int right = (m + n + 2) / 2;
            return (findMid(nums1, 0, nums2, 0, left) + findMid(nums1, 0, nums2, 0, right)) / 2.0;
        }
    
        private int findMid(int[] nums1, int i, int[] nums2, int j, int k) {
        
            if(i >= nums1.length) return nums2[j + k - 1];
            if(j >= nums2.length) return nums1[i + k - 1];
            if(k == 1) return Math.min(nums1[i], nums2[j]);
            int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
            int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
            if(midVal1 < midVal2) {
        
                return findMid(nums1, i + k / 2, nums2, j, k - k / 2);
            }else {
        
                return findMid(nums1, i, nums2, j + k / 2, k - k / 2);
            }
        }
    }

![在这里插入图片描述][20210120112251879.jpg_pic_center]

下面为两个数据测试的变量轨迹

示例一：

nums1 = {
        1, 4, 6, 10}
    nums2 = {
        2, 5, 7, 9}
    
    left = (4 + 4 + 1) / 2 = 4, 调用findMid()
    k = 4  i = 0 nums1[i] = 1 ,  j = 0 nums2[j] = 2
    k = 2  i = 2 nums1[i] = 6 ,  j = 0 nums2[j] = 2
    k = 1  i = 2 nums1[i] = 6 ,  j = 1 nums2[j] = 5
    findMid()返回 nums2[1] = 5
        
    right = (4 + 4 + 2) / 2 = 5, 调用findMid()
    k = 5  i = 0 nums1[i] = 1 ,  j = 0 nums2[j] = 2
    k = 3  i = 2 nums1[i] = 6 ,  j = 0 nums2[j] = 2
    k = 2  i = 2 nums1[i] = 6 ,  j = 1 nums2[j] = 5
    k = 1  i = 2 nums1[i] = 6 ,  j = 2 nums2[j] = 7
    findMid()返回 nums1[2] = 6

示例二：

nums1 = {
        1, 4, 6}
    nums2 = {
        2, 5, 7, 9}
    
    left = (3 + 4 + 1) / 2 = 4, 调用findMid()
    k = 4  i = 0 nums1[i] = 1 ,  j = 0 nums2[j] = 2
    k = 2  i = 2 nums1[i] = 6 ,  j = 0 nums2[j] = 2
    k = 1  i = 2 nums1[i] = 6 ,  j = 1 nums2[j] = 5
    findMid()返回 nums2[1] = 5
        
    right = (3 + 4 + 2) / 2 = 4, 同上

[LeetCode _ Offer 41.]: https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
[LeetCode 480.]: https://leetcode-cn.com/problems/sliding-window-median/
[LeetCode 4.]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/c7f6397d096c4537ba6938fcbb0d0286.png
[20210120112251879.jpg_pic_center]: https://img-blog.csdnimg.cn/20210120112251879.jpg#pic_center