即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

LeetCoder 4. Median of Two Sorted Arrays (有序数组合并的中位数)

编程语言 helloiamclh 11℃ 0评论
本文目录
[隐藏]

1.题意

两个有序数组A,B,求两个数组合并后的中位数

2.思路

解法一:


使用归并排序的思路,遍历两个有序数组,然后当遍历数为我们要找到的中位数的位置的时候,即可停止。时间复杂度O(n+m)


解法二:


根据中位数的定义可知,中位数左边的数小于等于中位数,中位数右边的数大于等于中位数,那么我门可以将左边的数看做一个集合leftPart,右边的数看做一个集合rightPart,当两个数组进行组合的时候,两个数组必定都会出现一个分割点,我们要找到这两个分割点,然后使得分割点左边的数都比中位数小,右边的数都比中位数大。


假设我们分割后的序列形式为

a[0],a[1],a[2],...,a[i - 1] | a[i], a[i + 1],...,a[n - 1]
b[0],b[1],b[2],...,b[j - 1] | b[j], b[j + 1],...,b[m - 1]

上面的n,m 为数组A,B的长度,切割点分别为ij,这个时候需要满足条件max(a[i1],b[j1])<=min(a[i],b[j]),才能确定i,j为我们要找到的切割点,此时的中位数为max(a[i1],b[j1])+min(a[i],b[j])2 .


如果数组A为较短的数组,且当前切割点为i,那么数组B的当前切割点也是确定了,通过等式i+j=n+m+12 (因为数组长度相加可能为奇数可能为偶数,所以说我们要考虑奇数的情况)求得,j=n+m+12i,所以说我们只需要找到正确的i,那么j也就求出来了.


在我们寻找满足条件的i 的时候,需要判断几种情况:


1. b[j1]>a[i]


这个时候说明我们切割点i 太小了,需要增加,当i 增加的时候,根据等式相应的j 会减小,那么有可能会找到


2. a[i1]>b[j]


这个时候说明我们切割点i 太大了,需要减小,当i,减小的时候,根据等式相应的j 会减小,那么有可能会找到


3. b[j1]<=a[i]a[i1]<=b[j]


这个时候说明我们找到了答案,但是需要处理一下边界情况(代码中很详细,不再赘述)

因为我们只是在一个数组中进行寻找切割点,且采用的是二分的方式,所以说时间复杂度为O(log(min(n,m)))

3.结果

Your runtime beats 72.67% of cpp submissions.

4.代码

class Solution {
public:
    double ans;
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        ans = -1;
        if(n > m){
            swap(n, m);
            findNum(nums2, nums1, 0, n, n, m, ans);
        }else{
            findNum(nums1, nums2, 0, n, n, m, ans);
        }
        return ans;
    }
private:
    void findNum(vector<int>& nums1, vector<int>& nums2, int L, int R, int n, int m, double &ans){
        if(ans >= 0) return ;
        if(L > R) return ;
        int i = (L + R) / 2;
        int j = (n + m + 1) / 2 - i;
        if(i < n && nums2[j - 1] > nums1[i]){
            findNum(nums1, nums2, i + 1, R, n, m, ans);
        } else if(i > 0 && nums1[i - 1] > nums2[j]){
            findNum(nums1, nums2, L, i - 1, n, m, ans);
        }else{
            int maxL, minR;
            if(i == 0) maxL = nums2[j - 1];
            else if(j == 0) maxL = nums1[i - 1];
            else maxL = max(nums1[i - 1], nums2[j - 1]);
            if((n + m) % 2 != 0){
                minR = -1;
            }else{
                if(i == n) minR = nums2[j];
                else if(j == m) minR = nums1[i];
                else minR = min(nums1[i], nums2[j]);
            }
            ans = (maxL + max(maxL, minR)) / 2.0;
        }
    }
};

转载请注明:CodingBlog » LeetCoder 4. Median of Two Sorted Arrays (有序数组合并的中位数)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情