Leetcode: Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

2017/2/5更新：如果一定要每次扔一半，使得时间复杂度为O(log(m+n))。可以在第一个数组找前k1个，第二个数组找前k2个，使得k1+k2 == k, 分情况：

1. if A[k1] < B[k2], then A[k1]及之前的、B[k2+1]及之后的都不可能成为第k个元素，所以扔掉

2. else if A[k1] > B[k2], then A[k1+1]及之后的、 B[k2]及之前的都不可能成为第k个元素。扔掉

One e.g. to explain:

x: x1 x2 | x3 x4 x5 x6

y: y1 y2 y3 y4 y5 | y6 y7 y8

We are currently looking for 7th element, where we compare 2nd element in x and 5th element in y

Note that if x2 < y6 then x2 < all the elements on the right side. Similarily, if y5 < x3, y5 < all the elements on the right side

if we know x2 < y5, we know that x2 can't be the 7th. Because we can't find possible enough candidates to be less than x2 if x2 < x3 and x2 < y5

y6 can't be either, y6 > y5, ans so y6 > x2. There are already k elements in front of y6

 1 public class Solution {
 2     public double findMedianSortedArrays(int A[], int B[]) {
 3         if((A.length+B.length)%2==1)
 4             return helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1);
 5         else
 6             return (helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2)  
 7                    +helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1))/2.0;
 8     }
 9     
10     private int helper(int A[], int B[], int i, int i2, int j, int j2, int k)
11     {
12         int m = i2-i+1;
13         int n = j2-j+1;
14         if(m>n)
15             return helper(B,A,j,j2,i,i2,k);
16         if(m==0)
17             return B[j+k-1]; //这是相对距离，不是相对于0，而是这轮起点j，所以决定了25行27行要减posA或posB
18         if(k==1)
19             return Math.min(A[i],B[j]);
20         int posA = Math.min(k/2,m);
21         int posB = Math.min(k-posA, n);
22 
23         if(A[i+posA-1]<B[j+posB-1])
24             return helper(A,B,i+posA,i2,j,j+posB-1,k-posA);
25         else
26             return helper(A,B,i,i+posA-1,j+posB,j2,k-posB);
27     }
28 }