Median of two Sorted Arrays 65

Question

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Example

Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Challenge

The overall run time complexity should be O(log (m+n)).

Solution

这道题是典型的二分＋DC。

1. 判断总元素数量n是奇数还是偶数。如果是奇数，则结果为第n/2+1个元素，如果是偶数，则结果为（第n／2元素+第n／2+1元素）／2。

2. 假设要找第k个元素。在A和B中分别寻找各自数组的第k/2个元素，比较两个找到的元素的大小，若A中元素小，则抛弃掉A中的k／2个元素，反之抛弃掉B中的k／2个元素，并继续寻找A和B中的第k（这里k＝k－k／2）个元素。

3. 几个边界条件：1）当其中一个数组元素全部被抛弃时，直接返回另一个数组中的第k个元素。2）如果k＝＝1，则直接返回两个数组中第一个元素较小的那一个。3）如果一个数组剩余元素不足k／2个，则抛弃另一个数组的k／2个元素（肯定不会将要找的第k个元素抛弃掉，因为就算不足的那个数组的元素也一起被抛弃掉，抛掉的元素还是不足k个）。

代码如下：

class Solution {
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        // write your code here
        int m = A.length, n = B.length;
        int k = m + n;
        if(k % 2 == 1){
            return findKth(A, 0, B, 0, k/2 + 1);
        }else{
            return (findKth(A, 0, B, 0, k/2) + findKth(A, 0, B, 0, k/2 + 1))/2;
        }
    }

    public double findKth(int[] A, int Astart, int[] B, int Bstart, int k){
        if(Astart >= A.length){
            return (double) B[Bstart + k - 1];
        }
        if(Bstart >= B.length){
            return (double) A[Astart + k - 1];
        }

        if(k == 1){
            return Math.min(A[Astart], B[Bstart]);
        }

        int A_key = Astart + k/2 - 1 < A.length? A[Astart + k/2 - 1] : Integer.MAX_VALUE;
        int B_key = Bstart + k/2 - 1 < B.length? B[Bstart + k/2 - 1] : Integer.MAX_VALUE;

        if(A_key < B_key){
            return findKth(A, Astart + k/2, B, Bstart, k - k/2);
        }else{
            return findKth(A, Astart, B, Bstart + k/2, k - k/2);
        }
    }
}