Leetcode 4. Median of Two Sorted Arrays

题目链接 Leetcode 4. Median of Two Sorted Arrays

　　题目描述很简单，就是找到两个有序数组合并后的中位数，要求时间复杂度O(log (m+n))。

　　如果不要去时间复杂度，很容易就想到了归并排序，归并排序的时间复杂度是O(m+n)，空间复杂度也是O(m+n)，不满足题目要求，其实我开始也不知道怎么做，后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。

代码如下：

class Solution {
    private int getkth(int[] A, int as, int[] B, int bs, int k) {
        if (as > A.length - 1) return B[bs + k - 1];
        if (bs > B.length - 1) return A[as + k - 1];
        if (k == 1) return Math.min(A[as], B[bs]);

        int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
        if (as + k/2 - 1 < A.length) aMid = A[as + k/2 - 1];
        if (bs + k/2 - 1 < B.length) bMid = B[bs + k/2 - 1];

        if (aMid < bMid)
            return getkth(A, as + k/2, B, bs, k - k/2);
        else
            return getkth(A, as, B, bs + k/2, k - k/2);
    }
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int l = (m + n + 1) / 2;
        int r = (m + n + 2) / 2;
        return (getkth(nums1, 0, nums2, 0, l) + getkth(nums1, 0, nums2, 0, r)) / 2.0;
    }
}

~谢谢打赏~

赏