LintCode: Median of two Sorted Arrays

更新时间：2022-09-08 20:52:59

求第k个值

1.归并排序

归并到第k个值为止

时间复杂度：O(k)

 1 class Solution {
 2 public:
 3     // merge-sort to find K-th value
 4     double helper(vector<int> A, vector<int> B, int lenA, int lenB, int k) {
 5         int i = 0, j = 0;
 6         while ((i < lenA) && (j < lenB)) {
 7             k--;
 8             if (A[i] < B[j]) {
 9                 if (0 == k) {
10                     return A[i];
11                 }
12                 ++i;
13             } else if (0 == k) {
14                 return B[j];
15             } else {
16                 ++j;
17             }
18         }
19         return (i >= lenA)?B[j + k - 1]:A[i + k - 1];
20     }
21     /**
22      * @param A: An integer array.
23      * @param B: An integer array.
24      * @return: a double whose format is *.5 or *.0
25      */
26     double findMedianSortedArrays(vector<int> A, vector<int> B) {
27         // write your code here
28         int m = A.size();
29         int n = B.size();
30         return ((m + n) & 1)?
31         (helper(A, B, m, n, (m + n + 1)>>1)):
32         (((helper(A, B, m, n, ((m + n)>>1) + 1))+(helper(A, B, m, n, (m + n)>>1))) * .5);
33     }
34 };

2. 分治法

利用归并的思想，从a和b中一共取k个数

假设len(a)<len(b)

从a中取pa ＝ min(k/2, len(a))个元素;

从b中取pb ＝ k-pa个元素；

如果a[pa - 1]<b[pb - 1]，则归并排序时先归并a[pa - 1]，说明a数组的数取“少”了，不够用

　　a到终点后，只用b的数凑足了k个，这说明总的第k大的值不会出现在a[0...pa-1]里边，所以我们扔掉前pa个数

　　对于b数组，说明总的第k大的数不会出现在b[pb...lenB]里边，pb后边的数就没用了

如果a[pa - 1]>=b[pb - 1]，是对称情况

　　归并排序时，会先归并b[pb － 1]，说明b数组的数取“少”了，不够用

　　b到终点后，只用a的数凑足了k个，这说明总的第k大的值不会出现在b[0...pb-1]里边，所以我们扔掉前pb个数

　　对于a数组，说明第k大的数不会出现在a[pa...lenA]里边，pa的后边就没用了

总结：扔掉较小数组的前一部分，扔掉较大数组的后一部分

复杂度分析：O(logK), K每次几乎减少一半

 1 class Solution {
 2 public:
 3     // merge-sort to find K-th value
 4     double helper(int *A, int *B, int lenA, int lenB, int k) {
 5         if (lenA > lenB) {
 6             return helper(B, A, lenB, lenA, k);
 7         }
 8         // lenA <= lenB
 9         if (lenA == 0) {
10             return B[k - 1];
11         }
12         if (1 == k) {
13             return min(A[0], B[0]);
14         }
15         int pa = min(lenA, k >> 1), pb = k - pa;
16         return (A[pa - 1] < B[pb - 1])?
17         helper(A + pa, B, lenA - pa, lenB, k - pa):
18         helper(A, B + pb, lenA, lenB - pb, k - pb);
19     }
20     /**
21      * @param A: An integer array.
22      * @param B: An integer array.
23      * @return: a double whose format is *.5 or *.0
24      */
25     double findMedianSortedArrays(vector<int> A, vector<int> B) {
26         // write your code here
27         int m = A.size();
28         int n = B.size();
29         return ((m + n) & 1)?
30         (helper(A.data(), B.data(), m, n, (m + n + 1)>>1)):
31         (((helper(A.data(), B.data(), m, n, ((m + n)>>1) + 1))+(helper(A.data(), B.data(), m, n, (m + n)>>1))) * .5);
32     }
33 };

本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/5009273.html，如需转载请自行联系原作者

上一篇 : ：Linux netstat命令介绍下一篇 : POJ2965

LintCode: Median of two Sorted Arrays

相关阅读

推荐文章