10

Leetcode 4. Median of Two Sorted Arrays

 3 years ago
source link: https://zxs.io/article/1189
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Leetcode 4. Median of Two Sorted Arrays
当前位置：XINDOO > 编程 > 正文

题目链接 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;
    }
}
赏

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK