Created
October 27, 2013 10:12
-
-
Save zsh-89/7179977 to your computer and use it in GitHub Desktop.
Leetcode: Median of Two Sorted Arrays.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
double findMedianSortedArrays(int A[], int m, int B[], int n) { | |
int N = m+n; | |
if (N%2) return findKth(A, m, B, n, N/2+1); | |
else return (double(findKth(A, m, B, n, N/2)) + findKth(A, m, B, n, N/2+1))/2; | |
} | |
int findKth(int A[], int m, int B[], int n, int k) { | |
if (m > n) return findKth(B, n, A, m, k); | |
if (m==0) return B[k-1]; | |
if (k==1) return min(A[0], B[0]); | |
int t = min(k/2, m); | |
int t2 = k-t; | |
if (A[t-1] < B[t2-1]) | |
return findKth(A+t, m-t, B, n, k-t); | |
else return findKth(A, m, B+t2, n-t2, k-t2); | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
这道题应该是在大众点评二面之前看过解法的。
在leetcode discuss区,这个解法没有被顶到第一名,真的很奇怪。
他的思路非常好,解决的不止是找到median,而是找到Kth biggest number。
利用findKth函数自身,把【从A,B中找第K大的数】,转换成【在A,B的子数组中找第K/2大的数】
Boundary Cases: