求第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，如需转载请自行联系原作者
