4. Median of Two Sorted Arrays *HARD* -- 查找两个排序数组的中位数（寻找两个排序数组中第k大的数）...-白红宇

4. Median of Two Sorted Arrays *HARD* -- 查找两个排序数组的中位数（寻找两个排序数组中第k大的数）...

阅读量：5280 次

发布时间：2019-06-14

本文共 1193 字，大约阅读时间需要 3 分钟。

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)).

t int MAX = 0x7fffffff, MIN = 0x80000000;int kth(vector
     
      & nums1, vector
      
       & nums2, int sz1, int sz2, int k){#define N1(i) (i<1?MIN:(i>sz1?MAX:nums1[i-1]))#define N2(i) (i<1?MIN:(i>sz2?MAX:nums2[i-1]))    int l, r, x;    l = 0;    r = sz1;    while (l <= r)    {        x = (l + r) >> 1;        if (N1(x) > N2(k - x + 1))            r = x - 1;        else if (N1(x + 1) < N2(k - x))            l = x + 1;        else            return max(N1(x), N2(k - x));    }    return 0; //should not get here#undef N1#undef N2}double findMedianSortedArrays(vector
       
        & nums1, vector
        
         & nums2) {    int sz1 = nums1.size(), sz2 = nums2.size(), sz = sz1 + sz2;    if (sz1 > sz2)        return findMedianSortedArrays(nums2, nums1);    if (sz & 1)        return kth(nums1, nums2, sz1, sz2, (sz >> 1) + 1);    return (kth(nums1, nums2, sz1, sz2, sz >> 1) + kth(nums1, nums2, sz1, sz2, (sz >> 1) + 1)) / 2.0;}