`
chriszeng87
  • 浏览: 736780 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

leetcode之 median of two sorted arrays

阅读更多

另一种方法即是利用类似merge的操作找到中位数,利用两个分别指向A和B数组头的指针去遍历数组,然后统计元素个数,直到找到中位数,此时算法复杂度为O(n)。之后还尝试了根据算法导论中的习题(9.3-8)扩展的方法,但是该方法会存在无穷多的边界细节问题,而且扩展也不见得正确,这个可从各网页的评论看出,非常不建议大家走这条路。

最后从medianof two sorted arrays中看到了一种非常好的方法。原文用英文进行解释,在此我们将其翻译成汉语。该方法的核心是将原问题转变成一个寻找第k小数的问题(假设两个原序列升序排列),这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题,原问题也得以解决。

首先假设数组A和B的元素个数都大于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]的元素都在A和B合并之后的前k小的元素中。换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。

证明也很简单,可以采用反证法。假设A[k/2-1]大于合并之后的第k小值,我们不妨假定其为第(k+1)小值。由于A[k/2-1]小于B[k/2-1],所以B[k/2-1]至少是第(k+2)小值。但实际上,在A中至多存在k/2-1个元素小于A[k/2-1],B中也至多存在k/2-1个元素小于A[k/2-1],所以小于A[k/2-1]的元素个数至多有k/2+ k/2-2,小于k,这与A[k/2-1]是第(k+1)的数矛盾。

当A[k/2-1]>B[k/2-1]时存在类似的结论。

当A[k/2-1]=B[k/2-1]时,我们已经找到了第k小的数,也即这个相等的元素,我们将其记为m。由于在A和B中分别有k/2-1个元素小于m,所以m即是第k小的数。(这里可能有人会有疑问,如果k为奇数,则m不是中位数。这里是进行了理想化考虑,在实际代码中略有不同,是先求k/2,然后利用k-k/2获得另一个数。)

通过上面的分析,我们即可以采用递归的方式实现寻找第k小的数。此外我们还需要考虑几个边界条件:

 

  • 如果A或者B为空,则直接返回B[k-1]或者A[k-1];
  • 如果k为1,我们只需要返回A[0]和B[0]中的较小值;
  • 如果A[k/2-1]=B[k/2-1],返回其中一个;

 

最终实现的代码为:

  1. double findKth(int a[], int m, int b[], int n, int k)  
  2. {  
  3.     //always assume that m is equal or smaller than n  
  4.     if (m > n)  
  5.         return findKth(b, n, a, m, k);  
  6.     if (m == 0)  
  7.         return b[k - 1];  
  8.     if (k == 1)  
  9.         return min(a[0], b[0]);  
  10.     //divide k into two parts  
  11.     int pa = min(k / 2, m), pb = k - pa;  
  12.     if (a[pa - 1] < b[pb - 1])  
  13.         return findKth(a + pa, m - pa, b, n, k - pa);  
  14.     else if (a[pa - 1] > b[pb - 1])  
  15.         return findKth(a, m, b + pb, n - pb, k - pb);  
  16.     else  
  17.         return a[pa - 1];  
  18. }  
  19.   
  20. class Solution  
  21. {  
  22. public:  
  23.     double findMedianSortedArrays(int A[], int m, int B[], int n)  
  24.     {  
  25.         int total = m + n;  
  26.         if (total & 0x1)  
  27.             return findKth(A, m, B, n, total / 2 + 1);  
  28.         else  
  29.             return (findKth(A, m, B, n, total / 2)  
  30.                     + findKth(A, m, B, n, total / 2 + 1)) / 2;  
  31.     }  
  32. };  

我们可以看出,代码非常简洁,而且效率也很高。在最好情况下,每次都有k一半的元素被删除,所以算法复杂度为logk,由于求中位数时k为(m+n)/2,所以算法复杂度为log(m+n)。

 

转自:http://blog.csdn.net/yutianzuijin/article/details/11499917/

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics