Code & Func

第21天，尝试了一下hard，结果是完全没做出来。。。从早上8点多到11点半，一直没能AC，最后只好看dicuss中的解法了，然后理解还理解了很久。。。看了现在的我还不适合做hard级别的。

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

因为没做出来，所以只能写写别人的思路了。

我们现在要找的是中位数，那么就有两种情况：

整体长度是奇数，那么中位数是序列中的数
整体长度是偶数，那么中位数是序列中两个数的平均值。

先考虑奇数的情况，因为是序列中的数，所以我们现在要求的就是在两个序列中第（size)/2 + 1大的数。

现在问题转换成在两个序列中求第k个数：

不断的将k减半，并把小的数从序列中排出，每次都能排出掉k/2.

1
double getKth(vector<int> &nums1,int beg1,int size1,vector<int> &nums2,int beg2,int size2,int k) {
2
        //cout << beg1<<" " <<size1<<"\t"<<beg2<<" "<<size2<<"\t"<<k<<endl;
3
        if (size1 > size2) {
4
                return getKth(nums2,beg2,size2,nums1,beg1,size1,k);
5
        }
6

7
        if (size1 == 0) { return nums2[beg2 + k-1];}
8
        if (k == 1) return min(nums1[beg1],nums2[beg2]);
9

10
        int i = min(size1,k/2);
11
        int j = min(size2,k/2);
12

13
        if (nums1[beg1 + i-1] > nums2[beg2 + j-1]) {
14
            return getKth(nums1,beg1,size1,nums2,beg2+j,size2-j,k-j);
15
        } else
2 collapsed lines
16
            return getKth(nums1,beg1+i,size1-i,nums2,beg2,size2,k-i);
17
    }

考虑偶数的情况，我们只要找出第(size)/2 + 1和(size)/2的大的数的平均值即可。

将两者统一一下：

1
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
2
    int l = (nums1.size() + nums2.size() + 1) >> 1;
3
    int r = (nums1.size() + nums2.size() + 2) >> 1;
4
    //cout << "#" << l << r << endl;
5
    double dl = getKth(nums1,0,nums1.size(),nums2,0,nums2.size(),l);
6
    double dr = getKth(nums1,0,nums1.size(),nums2,0,nums2.size(),r);
7
    //cout << dl <<dr << endl;
8
    return (dr+dl)/2;
9
}

恩，等下次感觉有能力做了，在来尝试一次！！！