栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

leetcode 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数(困难)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

leetcode 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数(困难)

一、题目大意

标签: 查找

https://leetcode.cn/problems/median-of-two-sorted-arrays

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

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

提示:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106
二、解题思路

号称leetcode守门员的题。中位数可以来自于同一个数组,也可以来自于两个数组,可以是一个数,也可以是两个数。
实现思路(参考花花酱的讲解)
分类:


思路:假设n1,n2是两个数组的元素,那么k=(n1+n2+1)/2就表示左中位数或中位数的索引,假设从nums1中取m1个元素,从nums2中取m2个元素,那么m1+m2 = k。我们要求的中位数就是从max(nums[m1-1], nums[m2-1])和min(nums[m1], nums[m2])。

三、解题方法 3.1 Java实现
public class Solution2 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        // 对长度小的数组做二分搜索
        if (n1 > n2 ) {
            return findMedianSortedArrays(nums2, nums1);
        }

        // 偶数情况:nums1=>[1, 2, 3] nums2=>[3, 4, 5]  中位数 2 3
        // 奇数情况:nums1=>[1, 2, 3] nums2=>[2, 3, 4, 5] 中位数 3
        // nums1=>[-1, 1, 3, 5, 7, 9] nums2=>[2, 4, 6, 8, 10, 12, 14, 16]
        int l = 0;
        int r = n1;
        // 偶数情况:左中位数 奇数情况:中位数
        int k = (n1 + n2 + 1) / 2;
        while (l < r) {
            int m1 = l + (r - l) / 2;
            int m2 = k - m1;
            if (nums1[m1] < nums2[m2-1]) {
                l = m1 + 1;
            } else {
                r = m1;
            }
        }
        int m1 = l;
        int m2 = k - l;

        int c1 = Math.max(m1 < 1 ? Integer.MIN_VALUE : nums1[m1-1], m2 < 1 ? Integer.MIN_VALUE : nums2[m2-1]);
        // 奇数情况
        if ((n1 + n2) % 2 == 1) {
            return c1;
        }

        int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) * 0.5;
    }
}
四、总结小记
  • 2022/5/30 做不出来的题就参考别人的吧,再转为自己的思路吧
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936250.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号