LeetCode #4 Median of Two Sorted Arrays 找中位数 二分

Description

---

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

给定两个排序好的数组，它们的大小分别是 m 和 n，找出这两个数组的中位数，要求整体运行时间复杂度为 O(log(m + n))。

 example：

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

The median is 2.0

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

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

思路

---

　　一看到给定的数组是已排序的和时间复杂度要求为 O(log(m + n)) ，就立马联想到用二分查找、归并，我先用归并做了这道题，虽然时间复杂度是 O(n)，但是经过优化后的算法执行时间也还是不错 。

　　暴力归并的思路很简单，开一个辅助空间 C，利用索引 i1 与 i2 对 num1[i1] 与 num2[i2] 进行比较，并将最小的值存入 C 中，最后奇偶情况输出 C 中的中位数即可。

　　我们可以对归并算法进行空间上的优化，由于 C 的中位数位于表长一半的位置，那么表长的后半部分其实可以不用存。而且，由于本题的解只需要返回一个 double 型的中位数，我们不需要真的去创建一个数组而是用 res1 res2，当 C 的索引到达中间的位置时，存储 C 最后的两个元素并根据奇偶情况输出即可，这样可以减少空间的开销。　　

//Runtime: 52 ms
#include<algorithm>
using std::min;
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.empty() && nums2.empty()) {
            return 0;
        }
        int l1 = nums1.size(), l2 = nums2.size();
        int l3 = l1 + l2;
        int i1 = 0, i2 = 0, i3 = 0;
        int indexM1 = (l3-1)/2, indexM2 = l3/2; //the former for odd,the latter for even
        double res1 = 0, res2 = 0;
        //mergeSort
        while (i1 < l1 && i2 < l2) { 
            if (i3 > indexM2) {
                break;
            }
            if (i3 == indexM1) {
                res1 = min(nums1[i1],nums2[i2]);
            }
            if (i3 == indexM2) {
                res2 = min(nums1[i1],nums2[i2]);
            }
            if (nums1[i1] < nums2[i2]) {
                i1++;
            }
            else {
                i2++;
            }
            i3++;
        }
        
        while (i1 < l1) { //nums1 has element
            if (i3 > indexM2) {
                break;
            }
            if (i3 == indexM1) {
                res1 = nums1[i1];
            }
            if (i3 == indexM2) {
                res2 = nums1[i1];
            }
            i1++;
            i3++;  
        }
        while (i2 < l2) { //nums2 has element
            if (i3 > indexM2) {
                break;
            }
            if (i3 == indexM1) {
                   res1 = nums2[i2];
            }
            if (i3 == indexM2) {
                res2 = nums2[i2];
            }
            i2++;
            i3++;
        }
        
        //for odd,return res1;for even,return (res1 + res2)/2.0;
        if (l3%2 == 0) {
            return (res1 + res2)/2.0;
        }
        else {
            return res1;
        }
    }
};

　　但是归并算法的时间复杂度本质上还是 O(n) ，达不到本题的要求。要想进一步优化使时间复杂度有指数级的变化，只能改变策略，这里使用了一种“伪”二分查找，时间复杂度是 O(lg(n)^2) 。

　　首先，中位数的实质上是第 k 小的数，此时 k = (m+n)/2 ，若为偶数情况则则找出第 k+1 小的数并取平均值就好了。

　　我们设两个数组元素个数都大于 k/2 ，我们取出 A[k/2 - 1] 与 B[k/2 -1] ，它们分别表示 A 的第 K/2 小的元素与 B 的第 K/2 小的元素，若 A[k/2 - 1] <= B[k/2 -1] ，说明 A[0] 到 A[k/2 - 1] 在合并后的序列里都在第 k 小的数之前，也就是说 A[0...k/2-1] 不可能会大于第 k 小值，因此可以将其舍弃。

　　同理，对于 A[k/2 - 1] <= B[k/2 -1] 也存在类似的结论。

　　讨论一下这个算法的时间复杂度，由于每次处理的仅是一个数组的前 k/2 个元素，对于长度为 m 的数组，它的时间复杂度为 O(lg(m)) ，对于长度为 n 的数组，它的时间复杂度为 O(lg(n)) ，所以它的时间复杂度为 O(lg(m) * lg(n)) ，由于它并不是在整体意义上进行的二分查找，所以达不到 O(lgn)。

//Runtime: 59 ms
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if ((m+n)%2 == 0) {
            return (findKth (nums1, nums2, (m+n)/2) + findKth (nums1, nums2, (m+n)/2+1)) / 2.0;       
        }else { 
            return findKth (nums1, nums2, (m+n)/2 + 1);
        }
    }
private:    
    int findKth(const vector<int>& a, const vector<int>& b, int k) {
        int m = a.size(), n = b.size();
        if (m > n) {
            return findKth(b, a, k);
        }
        if (m == 0) {
            return b[k-1];
        }
        if (k == 1) {
            return std::min(a[k-1], b[k-1]);
        }
        int i = std::min(k/2, m), j = std::min(k/2, n);
        if (a[i-1] < b[j-1]) {            
            return findKth (vector<int>(a.begin()+i, a.end()), b, k-i);
        }else{
            return findKth (a, vector<int>(b.begin()+j,b.end()), k-j);
        }
    }   
};

　　有人利用了其他的方法，实现了整体意义上的二分查找，时间复杂度为 O(lg(m+n)) ，十分巧妙，由于我没有去实现，所以这里只给出方法的链接，共大家参考讨论

• 链接一
• 链接二