侧边栏壁纸
博主头像
Z同学博主等级

工作磨平激情前,坚持技术的热忱。 欢迎光临Z同学的技术小站。 分享最新的互联网知识。

  • 累计撰写 274 篇文章
  • 累计创建 55 个标签
  • 累计收到 74 条评论

LeetCode 第四题 寻找两个正序数组的中位数

Z同学
2022-01-27 / 0 评论 / 0 点赞 / 214 阅读 / 2,347 字
温馨提示:
本文最后更新于 2022-01-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1. 题目

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

参考示例:

示例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

示例4:
输入:nums1 = [], nums2 = [1]
输出:1.00000

示例5:
输入:nums1 = [2], nums2 = []
输出:2.00000

重要提示:

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

2. 答题

在答题前,我们得了解什么是中位数。

2.1 中位数

中位数:又称为中点数,中值。是按顺序排列的数组中居于中间位置的数。也就是说在这一个数组中,有一半比它大,有一半比它小。如果这个数组是奇数那么中位数就是中间那个数,而如果数组是个偶数,那么中间的两个数值的算术平均值就是这个数组的中位数。

示例1:

20、21、23、23、25、29、32、33 的中位数: 由于是偶数列,中间的数是23,25

那么中位数就是:(23+25)/ 2=24  。

示例2:
10、 20、 20、 20、 30 的中位数: 由于是奇数列,中间的数是20 那么中位数就是20。

2.2 解题

我们直观理解的话,就是拼接两个数组,并按照从小到大进行排序成一个新数组,并求取该数组的中位数。逻辑是不是很简单?

那么我们直接实现一下吧:

示例:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //将两个数组合并成一个数组
        int[] sumNums = Arrays.copyOf(nums1, nums1.length + nums2.length);
        System.arraycopy(nums2, 0, sumNums, nums1.length, nums2.length);
        //执行数组的排序  从小到大进行排序
        Arrays.sort(sumNums);
        //计算中位数
        int length = sumNums.length;
        double vales=0;
        if(length%2 == 0){
            //偶数, 因为数组从0开始,所以要除2之后减1。
            vales = (sumNums[length/2-1]+sumNums[length/2])/2D;
        }else{
            //奇数
            vales = sumNums[length/2];
        }
        return vales;
    }
}

image-20220127164552216

上面的代码比较简单。更多的都是使用java SDK中提供的api。

但是结果很明显, 能够计算出来,但是耗时速度和内存消耗。都并不理想。

因为两个数组并不是乱序而是正序,所以我们合并之后再处理排序。浪费了时间。

官方提供了一个示例:

class Solution {
      public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m;
        // median1:前一部分的最大值
        // median2:后一部分的最小值
        int median1 = 0, median2 = 0;

        while (left <= right) {// 一直循环找到一个最大的i满足A[i-1]≤B[j]
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            //当一个数组不出现在前一部分时,对应的值为负无穷,就不会对前一部分的最大值产生影响
            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
		   //当一个数组不出现在后一部分时,对应的值为正无穷,就不会对后一部分的最小值产生影响
            int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);

            if (nums_im1 <= nums_j) {
                median1 = Math.max(nums_im1, nums_jm1);
                median2 = Math.min(nums_i, nums_j);
                left = i + 1;
            } else {
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
}

输出结果:

image-20220127170226074

相较于我们直接循环,速度要有了显著提高。只是内存占用仍然比较高。

3. 引用

题目来自LeetCode:https://leetcode-cn.com/problems/median-of-two-sorted-arrays

0

评论区