Leetcode 4 Median of Two Sorted Arrays

triplebee

发布于 2018-01-12 15:18:50

3790

发布于 2018-01-12 15:18:50

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

想法题，但是也算不上hard难度，最优解法确实不太好想，刚开始想了一个二分的方法。

后来发现在最坏情况下，算法会退化为O(n+m)，于是有了下面的想法：

每次把前K小的名额均分为两半，分到两个数组中，每组获得这个名额的最大数进行PK。

小的一方分到名额的数在下次分配中可以不考虑，因为已经可以确定他们必定属于前K小。

同时下一次剩余的未分配名额减去本次筛选掉的名额。

如此反复，直到最后只剩一个名额，或者某一组没有数。

在每一组数的个数大于k/2个时，这种方法每次都可以稳定筛选掉k/2个数，因而不论什么样的情况，效率都不会明显退化。

下面看代码：

class Solution
{
public:
    double fun(vector<int> a,int sa,int ea,vector<int> b,int sb,int eb,int k)
    {
        if(ea+1-sa>eb+1-sb) //确保a的长度小于b，这样只用考虑a不足k/2的情况
            return fun(b,sb,eb,a,sa,ea,k);
        if(ea+1-sa == 0)//a中没有元素，返回b中第k大
            return b[k-1];
        if(k==1)//只剩一个名额
            return min(a[sa],b[sb]);
        int ta=min(ea+1-sa,k/2),tb=k-ta;//因为不知道较小的a会占用k/2还是自身长度的名额，所以作减法
        if(a[sa+ta-1]==b[sb+tb-1])//相等时，这两个数就是所求值
            return a[sa+ta-1];
        if(a[sa+ta-1]>b[sb+tb-1])//舍去较小的一部分
            return fun(a,sa,ea,b,sb+tb,eb,k-tb);
        return fun(a,sa+ta,ea,b,sb,eb,k-ta);
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        int len1=nums1.size();
        int len2=nums2.size();
        if((len1+len2)%2)//奇数一个值，偶数两个值均值
            return fun(nums1,0,len1-1,nums2,0,len2-1,(len1+len2+1)/2);
        else
            return (fun(nums1,0,len1-1,nums2,0,len2-1,(len1+len2)/2+1)+fun(nums1,0,len1-1,nums2,0,len2-1,(len1+len2)/2))/2;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-08-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

arrays