Thursday, November 13, 2014

[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)).

思路:难题
定义C为A和B合并而成的sorted array
m+n 奇数时:median为C第 (m+n)/2+1 个数
m+n 偶数时:median为C第 (m+n)/2 和第 (m+n)/2+1 个数的平均
问题转化为:如果已知A、B,和任意1<=k<=m+n,找到C中第k个数。其中C=sorted(merge(A,B))
比较A,B中任意两个数字A[i],B[j]。假设A[i],B[j]为C中第i'和j'个数。
1. 如果A[i] < B[j]:
B[j] > A[0:i]以及B[j]>=B[0:j-1] => B[j] => j' >= i+j+2
A[i] >= A[0:i-1]以及A[i]最多比B[0:j-1]大 => i' <= i+j+1
k> i+j+1,A[0:i]可以排除
k<= i+j+1,B[j:n-1]可以排除
2. 如果A[i] > B[j]:和1正好相反
k > i+j+1,B[0:j]可以排除 
k<= i+j+1,A[i:m-1]可以排除
3. 如果A[i] = B[j]:
A[i]>=A[0:i-1],A[i]>=B[0:j] => i' >= i+j+2
B[j]和A[i]的情况一样 j' >= i+j+2
k > i+j+1,A[0:i]可以排除(假如i' = i+j+2,k = i+j+2,由于A[i]=B[j]两者都可以为第i+j+2个数字,所以A[i]可以排除掉)
k <= i+j+1,B[j:n-1]可以排除
所以3可以合并到1中。

思路整理:
A[i] <= B[j]
k > i+j+1,搜索A[i+1:m-1]和B[0:n-1]中的第k-i-1个元素
k <= i+j+1,搜索A[0:m-1]和B[0:j-1]中的第k个元素
A[i] > B[j]
k > i+j+1,搜索A[0:m-1]和B[j+1:n-1]中的第k-j-1个元素
k <= i+j+1,搜索A[0:i-1]和B[0:n-1]中的第k个元素
base case: 
如果搜索A[s:e]且s>e,即A搜索完了,则直接返回B[k-1]。
如果搜索B[s:e]且s>e,即B搜索完了,则直接返回A[k-1]。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int mid = (m+n)/2;
        if((m+n)%2) // odd total length
            return (double)findKthNum(A, m, B, n, mid+1);
        else {
            int median1 = findKthNum(A, m, B, n, mid);
            int median2 = findKthNum(A, m, B, n, mid+1);
            return 0.5*((double)median1 + (double)median2);
        }
    }
    
    int findKthNum(int A[], int m, int B[], int n, int k) {
        if(m==0) return B[k-1];
        if(n==0) return A[k-1];
        int i = m/2, j = n/2;
        if(A[i]<=B[j]) {
            if(k>i+j+1)
                return findKthNum(A+i+1, m-i-1, B, n, k-i-1);
            else
                return findKthNum(A, m, B, j, k);
        }
        else {
            if(k>i+j+1)
                return findKthNum(A, m, B+j+1, n-j-1, k-j-1);
            else
                return findKthNum(A, i, B, n, k);
        }
    }
};

No comments:

Post a Comment