本页目录

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

null likes · null views · 2024-05-29

题目要求 $lo g$ 级别的算法，下面给出 $O (lo g min (m, n))$ 的解法，和官方题解的思路不太相同。

我的思路基于两个观察：

如果两个有序序列的中位数分别为 $a$ 和 $b$ ，那么合并后的序列的中位数一定在 $a$ 和 $b$ （闭区间）之间。

对于合并后的序列，同时删掉最小和最大的相同数量的元素，中位数不变。

第二点是显然的。对于第一点，如果合并序列的中位数 $c$ 同时大于 $a$ 和 $b$ ，那么原来两个序列中一定分别有多于半数的元素小于 $c$ ，此时合并序列中小于 $c$ 的元素个数也一定多于半数，与中位数定义矛盾。

基于上面两个观察，对短数组进行二分区间，同时也在长数组上维护一个区间，每次比较两个区间的中位数大小。假如短数组的中位数更大，那么短数组取区间的左半部分，相当于删掉了短数组右区间的k个元素；此时要相应地删掉长数组左区间的k个元素，以保证合并后的序列的中位数不变。

此解法的边界条件需要格外注意：

如果一方数组为空，则直接返回另一方的中位数。

如果区间包含了偶数个元素，则中间两个元素都要保留，以保证正确性。对于部分情况相当于区间要额外包含一个元素进来。（高亮行）

算法终止时，短数组区间长度可能是1或2个元素，最终的结果就是把这两个元素插入到长数组区间中，再取中位数。为了保证效率，不去做插入，而是讨论长数组区间中位数附近的元素。

注意上述第三点，假设长数组区间中位数情况为：[... a m b ...]或[... a m1 m2 b ...]，那么如果a和b存在（没越界）也要纳入考虑。这是因为如果短数组剩余的元素均小于a，则有可能中位数需要通过a和m（或m1）计算得到。反之亦然。体现在代码中，短数组可能向ans贡献1或2个元素，长数组可能向ans贡献1~4个元素。最后对至多含有6个元素的ans排序取中位数即可。

C++

class Solution {
public:
    double mid(vector<int>& arr)//返回数组中位数
    {
        return (arr[arr.size()/2]+arr[(arr.size()-1)/2])/2.0;
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size(),n=nums2.size();
        if(m==0) return mid(nums2);
        if(n==0) return mid(nums1);
        if(n<m) return findMedianSortedArrays(nums2,nums1);
        int l1=0,r1=m-1,l2=0,r2=n-1,m1,m2;
        while(l1+1<r1)
        {
            m1=l1+(r1-l1)/2,m2=l2+(r2-l2)/2;
            if(nums1[m1]+nums1[m1+(r1-l1)%2]<nums2[m2]+nums2[m2+(r2-l2)%2])
            {
                r2-=(m1-l1),l1=m1;
            }
            else
            {
                if((r1-l1+1)%2==0) m1++;
                l2+=(r1-m1),r1=m1;
            }
        }
        m2=l2+(r2-l2)/2;
        bool flag=(r2-l2)%2;//长数组剩余部分是否为偶数个
        vector<int> ans={nums1[l1],nums2[m2]};
        if(r1!=l1) ans.emplace_back(nums1[r1]);//短数组长度为2
        if(flag) ans.emplace_back(nums2[m2+1]);//长数组长度为偶数
        if(0<=m2-1&&m2+1+flag<n)//中位数左、右一个元素均不越界
        {
            ans.emplace_back(nums2[m2-1]);
            ans.emplace_back(nums2[m2+1+flag]);
        }
        sort(ans.begin(),ans.end());
        return mid(ans);
    }
};

Loading component...

class Solution { public: double mid(vector<int>& arr)//返回数组中位数 { return (arr[arr.size()/2]+arr[(arr.size()-1)/2])/2.0; } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m=nums1.size(),n=nums2.size(); if(m==0) return mid(nums2); if(n==0) return mid(nums1); if(n<m) return findMedianSortedArrays(nums2,nums1); int l1=0,r1=m-1,l2=0,r2=n-1,m1,m2; while(l1+1<r1) { m1=l1+(r1-l1)/2,m2=l2+(r2-l2)/2; if(nums1[m1]+nums1[m1+(r1-l1)%2]<nums2[m2]+nums2[m2+(r2-l2)%2]) { r2-=(m1-l1),l1=m1; } else { if((r1-l1+1)%2==0) m1++; l2+=(r1-m1),r1=m1; } } m2=l2+(r2-l2)/2; bool flag=(r2-l2)%2;//长数组剩余部分是否为偶数个 vector<int> ans={nums1[l1],nums2[m2]}; if(r1!=l1) ans.emplace_back(nums1[r1]);//短数组长度为2 if(flag) ans.emplace_back(nums2[m2+1]);//长数组长度为偶数 if(0<=m2-1&&m2+1+flag<n)//中位数左、右一个元素均不越界 { ans.emplace_back(nums2[m2-1]); ans.emplace_back(nums2[m2+1+flag]); } sort(ans.begin(),ans.end()); return mid(ans); } };