leetcode-寻找两个正序数组的中位数

点击：题目链接：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

思路

一种思路就是使用双指针，不断找到大数组的中位数，但是要注意的是，个数有奇偶之分

另一种思路,直接利用中位数：

1. 为了避免奇偶性的判断，我们也可以先将大数组填充为之前的两倍，保证个数肯定是双数。
2. 填充后，两个数组的中位数与大数组的关系就为，center1 +center2 = m+n
3. 使用两个数组的中位数与合并后大数组的关系 l1 < r2 && l2 < r1, l,r 分别是对应数组的中位数的相邻两个元素
4. 当其中大数组的中位数只出现在一个数组，说明此时另一个数组的数比当前的数组的数都要大或小，临界值可以表示为
   • center1 == 0, l1 = INT_MAX
   • cetner1 == m, r1 = INT_MIN
   • center2 == 0, l2 = INT_MAX
   • cetner2 == n, r2 = INT_MIN

代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
        
        int n = nums1.size();
        int m = nums2.size();

        int l1, r1, l2, r2, c1,c2,low = 0, high = 2*n;

        while(low<=high){

            //扩充之后的中位线
            c1 = (low+high)/2;
            c2 = m+n -c1;

            l1 = (c1 ==0)? INT_MIN:nums1[(c1-1)/2];
            r1 = (c1 == 2*n)? INT_MAX: nums1[(c1)/2];

            l2 = (c2==0)? INT_MIN:nums2[(c2-1)/2];
            r2 = (c2 == 2*m)?INT_MAX:nums2[(c2)/2];

            if(l1>r2){
                high = c1-1;
            }else if(l2>r1){
                low = c1+1;
            }else{
                break;
            }
        }

        return (max(l1,l2)+ min(r1,r2))/2.0;
    }
};

复杂度

时间O(log(min(m,n))),空间（1）