鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

LeetCode #4 Median of Two Sorted Arrays

来源:互联网 作者:佚名 时间:2018-01-25 11:26
Description There are two sorted arraysnums1andnums2of 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,找出这

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)) ,十分巧妙,由于我没有去实现,所以这里只给出方法的链接,共大家参考讨论

  • 链接一
  • 链接二
网友评论
<