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;
    }
}
打赏

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.