LeetCode 4.寻找两个正序数组的中位数 （二分查找）

题目描述

解法一：

• 申请两个堆，分别为大顶堆和小顶堆，可以用优先队列实现。
• 维护这两个堆，使得大顶堆里面的元素都小于小顶堆里面的元素，同时大顶堆里面元素的个数与小顶堆里面的元素个数相差不能超过1。
• 将数组里面的数都装入堆中后，则中位数就是两个堆的堆顶元素
  • 如果两个数组的元素之和为奇数的话就是堆中元素个数较多的堆顶元素。
  • 如果两个数组元素之和为偶数的话就是堆顶 元素的平均值。

    void pushNum(priority_queue<int,vector<int>,greater<int>>& mi, priority_queue<int>& ma, int num)
    {
        if(ma.size() > 0 && num <= ma.top())
            ma.push(num);
        else
            mi.push(num);
        adjust(mi,ma);
    }
    void adjust(priority_queue<int,vector<int>,greater<int>>& mi, priority_queue<int>& ma)
    {
        while(mi.size() < ma.size())
        {
            mi.push(ma.top());
            ma.pop();
        }
        while(mi.size() > ma.size())
        {
            ma.push(mi.top());
            mi.pop();
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() == 0 && nums2.size() == 0) return 0;
        priority_queue<int,vector<int>,greater<int>> mi;
        priority_queue<int> ma;
        for(auto n : nums1)
            pushNum(mi,ma,n);
        for(auto n : nums2)
           pushNum(mi,ma,n);
        double ans = 0;
        if(ma.size() == mi.size()) ans = (double)(ma.top() + mi.top()) / 2;
        else if(ma.size() > mi.size()) ans = ma.top();
        else ans = mi.top();
        return ans;
    }

时间复杂度：O（M + N）
空间复杂度：O（M + N）

解法二：
首先我们要知道中位数是什么：左边的所有数都小于它，右边的所有数的大于它
所以我们可以根据中位数的这个特点来：

• 首先我们找到nums1的中间位置i，为nums2的中间位置j
  • 此时如果左边的最大数小于等于右边的最小数，即max(num1[i-1],num2[j-1] <=max( num1[i+1],num2[j+1])那么此时就可以计算出中位数
  • 如果左边的最大数不小于等于右边的最小数，那么我们就需要想办法来更新使得它满足左边的最大数小于等于右边的最小数这种情况，但是如何更新呢？
    • 首先我们知道每个数组都是有序的，所以必然有num1[i-1] <= num1[i+1],num2[j-1]<=num2[j+1];因此我们只需要保证num1[i-1] <= num2[j+1] && num2[j-1] <= num1[i+1]就可以了。
    • 如果num1[i-1] > num2[j+1],我们就将i左移动，此时j = ( m + n + 1) / 2 - i;
    • 如果num2[j-1] > num1[i+1],我们就将i右移动，此时 j = ( m + n + 1) / 2 - i;
    • 重复此过程直到满足条件位置

注意：为了保证 0 <=j <= n所以就所对应的数组一定要是两个数组中最长的数组

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m -   1, right)) * 0.5;  
    }
    
    int getKth(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k)     {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return min(nums1[start1], nums2[start2]);

        int i = start1 + min(len1, k / 2) - 1;
        int j = start2 + min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

时间复杂度：O( log（min（m，n））
空间复杂度：O（1）