AI工具人
提示词工程师

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;
    }
}
赞(0) 打赏
未经允许不得转载:XINDOO » Leetcode 4. Median of Two Sorted Arrays

评论 抢沙发

觉得文章有用就打赏一下文章作者

非常感谢你的打赏,我们将继续给力更多优质内容,让我们一起创建更加美好的网络世界!

支付宝扫一扫

微信扫一扫