## Wednesday, December 26, 2012

### [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)).
» Solve this problem

[解题思路]
O(n)的解法比较直观，直接merge两个数组，然后求中间值。而对于O(log(m+n))显然是用二分搜索了， 相当于“Kth element in 2 sorted array”的变形。如果(m+n)为奇数，那么找到“(m+n)/2+1 th element in 2 sorted array”即可。如果（m+n）为偶数，需要找到(m+n)/2 th 及(m+n)/2+1 th，然后求平均。

If (m/2+n/2+1) > k && am/2 > bn/2 , drop Section 2
If (m/2+n/2+1) > k && am/2 < bn/2 , drop Section 4
If (m/2+n/2+1) < k && am/2 > bn/2 ,  drop Section 3
If (m/2+n/2+1) < k && am/2 < bn/2drop Section 1

[Code]

``````1:    double findMedianSortedArrays(int A[], int m, int B[], int n) {
2:      if((n+m)%2 ==0)
3:      {
4:        return (GetMedian(A,m,B,n, (m+n)/2) + GetMedian(A,m,B,n, (m+n)/2+1))/2.0;
5:      }
6:      else
7:        return GetMedian(A,m,B,n, (m+n)/2+1);
8:    }
9:       int GetMedian(int a[], int n, int b[], int m, int k)
10:       {
11:            assert(a && b);
12:            if (n <= 0) return b[k-1];
13:            if (m <= 0) return a[k-1];
14:            if (k <= 1) return min(a[0], b[0]);
15:            if (b[m/2] >= a[n/2])
16:            {
17:                 if ((n/2 + 1 + m/2) >= k)
18:                      return GetMedian(a, n, b, m/2, k);
19:                 else
20:                      return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1));
21:            }
22:            else
23:            {
24:                 if ((m/2 + 1 + n/2) >= k)
25:                      return GetMedian( a, n/2,b, m, k);
26:                 else
27:                      return GetMedian( a, n, b + m/2 + 1, m - (m/2 + 1),k - (m/2 + 1));
28:            }
29:       }
``````

[注意]

[Rank]