[LintCode 题解] 阿里巴巴面试算法题：两个排序数组的中位数

[hakunamatata11]

题目描述

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

说明

中位数的定义：

• 这里的中位数等同于数学定义里的中位数。
• 中位数是排序后数组的中间值。
• 如果有数组中有 n 个数且 n 是奇数，则中位数为 A[(n-1)/2]A[(n−1)/2]。
• 如果有数组中有 n 个数且 n 是偶数，则中位数为 (A[n / 2] + A[n / 2 + 1]) / 2(A[n/2]+A[n/2+1])/2.
• 比如：数组 A=[1,2,3]的中位数是 2，数组 A=[1,19]的中位数是 10。

样例 1

输入:
A = [1,2,3,4,5,6]
B = [2,3,4,5]
输出: 3.5

样例 2

输入:
A = [1,2,3]
B = [4,5]
输出: 3

题解

分治法。时间复杂度 log(n + m)log(n+m)

这题是面试高频题，除了分治法外，还有二分法等其他方法来解，点击链接立即免费试听：https://www.jiuzhang.com/course/9/?utm_source=sc-v2ex-fks免费试听，攻略还有更多大厂常考题型。

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int n = A.length + B.length;

        if (n % 2 == 0) {
            return (
                findKth(A, 0, B, 0, n / 2) + 
                findKth(A, 0, B, 0, n / 2 + 1)
            ) / 2.0;
        }

        return findKth(A, 0, B, 0, n / 2 + 1);
    }

    // find kth number of two sorted array
    public static int findKth(int[] A, int startOfA,
                              int[] B, int startOfB,
                              int k){       
        if (startOfA >= A.length) {
            return B[startOfB + k - 1];
        }
        if (startOfB >= B.length) {
            return A[startOfA + k - 1];
        }

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

        int halfKthOfA = startOfA + k / 2 - 1 < A.length
            ? A[startOfA + k / 2 - 1]
            : Integer.MAX_VALUE;
        int halfKthOfB = startOfB + k / 2 - 1 < B.length
            ? B[startOfB + k / 2 - 1]
            : Integer.MAX_VALUE; 

        if (halfKthOfA < halfKthOfB) {
            return findKth(A, startOfA + k / 2, B, startOfB, k - k / 2);
        } else {
            return findKth(A, startOfA, B, startOfB + k / 2, k - k / 2);
        }
    }
}