Java教程

[LeetCode]4.寻找两个正序数组的中位数(Java)

本文主要是介绍[LeetCode]4.寻找两个正序数组的中位数(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题地址: median-of-two-sorted-arrays

题目描述:

示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例 3:
输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000

提示:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗?

解答方法:

1.nums1,nums2合并后排序

时间复杂度:遍历全部数组 O(m+n)
空间复杂度:开辟了一个数组,保存合并后的两个数组 O(m+n)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] res=new int[nums1.length + nums2.length];
        int n = 0;
        int len = nums1.length + nums2.length;
        for (int i = 0; i < nums1.length; i++){
            res[i] = nums1[i];
        }
        for (int i = nums1.length; i < res.length; i++){
            res[i] = nums2[n];
            n++;
        }
        Arrays.sort(res);
        if(len % 2 == 0){
            return (double)(res[len/2] + res[len/2 - 1])/2;
        }else{
            return res[len/2];
        }
    }
}

问题:

  • 拷贝产生新的数组从而增加时间复杂度,而题目限制了时间复杂度为 O(log (m+n)),没达到要求。

2.二分法

用到二分的方法才能达到 O(log(m+n))
分别找第 (m+n+1) / 2 个,和 (m+n+2) / 2 个,然后求其平均值即可,对奇偶数均适用。
由于数列是有序的,其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数,我们可以每次循环排除掉 k/2 个数。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
//将偶数和奇数的情况合并,如果是奇数,会求两次同样的 k 。
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}

private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
    int len1 = end1 - start1 + 1;
    int len2 = end2 - start2 + 1;
    //让 len1 的长度小于 len2,这样就能保证如果有数组空了,一定是 len1 
    if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
    if (len1 == 0) return nums2[start2 + k - 1];

    if (k == 1) return Math.min(nums1[start1], nums2[start2]);

    int i = start1 + Math.min(len1, k / 2) - 1;
    int j = start2 + Math.min(len2, k / 2) - 1;

    if (nums1[i] > nums2[j]) {
        return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
    }
    else {
        return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
    }
}
这篇关于[LeetCode]4.寻找两个正序数组的中位数(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!