LeetCode: Median of Two Sorted Arrays

这题难度在编程，看了网上答案

 1 class Solution {
 2 public:
 3     int dfs(int A[], int m, int B[], int n, int k)  
 4     { 
 5         if (m <= 0) return B[k-1];  
 6         if (n <= 0) return A[k-1];  
 7         if (k <= 1) return min(A[0], B[0]);   
 8         if (B[n/2] >= A[m/2]  && (m/2+n/2+1 >= k)) return dfs(A, m, B, n/2, k);
 9         if (B[n/2] >= A[m/2]  && (m/2+n/2+1 < k)) return dfs(A+m/2+1, m-m/2-1, B, n, k-(m/2+1));
10         if (B[n/2] < A[m/2]  && (m/2+n/2+1 >= k)) return dfs(A, m/2, B, n, k);
11         if (B[n/2] < A[m/2]  && (m/2+n/2+1 < k)) return dfs(A, m, B+n/2+1, n-n/2-1, k-(n/2+1));
12     }
13     double findMedianSortedArrays(int A[], int m, int B[], int n) {
14         // Start typing your C/C++ solution below
15         // DO NOT write int main() function
16         if((n+m)%2)  return dfs(A,m,B,n, (m+n)/2+1);   
17         else return (dfs(A, m, B, n, (m+n)/2) + dfs(A, m, B, n, (m+n)/2+1))/2.0;
18     }
19 };

再贴段比较容易懂的代码

 1 class Solution {
 2 public:
 3     double dfs(int A[], int m, int B[], int n, int k) {
 4         if (!m) return B[k-1];
 5         if (!n) return A[k-1];
 6         int *p, *q;
 7         if (A[m/2] <= B[n/2]) p = A, q = B;
 8         else {
 9             p = B, q = A;
10             swap(m, n);
11         }
12         if (k <= m/2+n/2+1) return dfs(p, m, q, n/2, k);
13         else return dfs(p+m/2+1, m-m/2-1, q, n, k-m/2-1);
14     }
15     double findMedianSortedArrays(int A[], int m, int B[], int n) {
16         // Start typing your C/C++ solution below
17         // DO NOT write int main() function
18         int k = m + n;
19         if (k % 2) return dfs(A, m, B, n, k/2+1);
20         else return (dfs(A, m, B, n, k/2+1)+dfs(A, m, B, n, k/2))/2;
21     }
22 };