65. 两个排序数组的中位数

描述

两个排序的数组A和B，分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))

样例

给出数组A = [1,2,3,4,5,6] B = [2,3,4,5]，中位数3.5
给出数组A = [1,2,3] B = [4,5]，中位数 3

挑战

时间复杂度为O(log n)

思路

根据时间复杂度寻找算法，所谓logk的时间复杂度就是在O(1)的时间使得规模为n的问题变为n/2;
通过比较两个数组k/2位置的值大小丢掉值较小一个数组中k/2个数

代码

public 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) {
        int len = A.length + B.length;
        if (len % 2 == 1) {
            return findKth(A, 0, B, 0, len / 2 + 1);
        } else {
            return (findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)) / 2.0;
        }
    }
    
    // k 是整个排序数组(两个数组合并后)的中位数
    public static int findKth(int[] A,
                              int A_startIndex,
                              int[] B,
                              int B_startIndex,
                              int k) {
        // 各种异常情况     
        // A 数组最后一个下标是 A.length - 1;                     
        if (A_startIndex >= A.length) {
            return B[B_startIndex + k - 1];
        } 
        if (B_startIndex >= B.length) {
            return A[A_startIndex + k - 1];
        }
        
        // 递归出口
        if (k == 1) {
            return Math.min(A[A_startIndex], B[B_startIndex]);
        }

        // 比较A数组和B数组的第k/2个数的大小,哪个小把哪个数组的前k/2个数抛掉
        int A_key = Integer.MAX_VALUE;
        int B_key = Integer.MAX_VALUE;
        if (A_startIndex + k / 2 - 1 < A.length) {
            A_key = A[A_startIndex + k / 2 - 1];
        }
        if (B_startIndex + k / 2 - 1 < B.length) {
            B_key = B[B_startIndex + k / 2 - 1];
        }
        // 抛掉k/2个数,通过O(1)的操作使问题的规模减小一半
        if (A_key < B_key) {
            return findKth(A, A_startIndex + k / 2, B, B_startIndex, k - k / 2 );
        } else {
            return findKth(A, A_startIndex, B, B_startIndex + k / 2, k - k / 2);
        }
    }
}