首页 > 其他分享 >【二分查找】LeetCode 4. 寻找两个正序数组的中位数

【二分查找】LeetCode 4. 寻找两个正序数组的中位数

时间:2023-03-07 14:01:14浏览次数:58  
标签:正序 int 中位数 VALUE nums1 length Integer LeetCode nums2

题目链接

4. 寻找两个正序数组的中位数

思路

分治

代码

class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;

        // 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;
        int totalLeft = (m + n + 1) / 2;

        // 在 nums1 的区间 [0, m] 里查找恰当的分割线,
        // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
        int left = 0;
        int right = m;

        while(left < right){
            int i = left + (right - left) / 2;
            int j = totalLeft - i;
            if(nums2[j - 1] > nums1[i]){
                // 下一轮搜索的区间 [i + 1, right]
                left = i + 1;
            }else{
                // 下一轮搜索的区间 [left, i]
                right = i;
            }
        }

        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if(((m + n) % 2) == 1){
            return Math.max(nums1LeftMax, nums2LeftMax);
        }else{
            return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
        }
    }
}

标签:正序,int,中位数,VALUE,nums1,length,Integer,LeetCode,nums2
From: https://www.cnblogs.com/shixuanliu/p/17187908.html

相关文章

  • LEETCODE 1096. 花括号展开 II
    这个题把题目中的表达式并列关系看做是求和,把相接看做是求积,那么求解整个表达式的过程可以类比于求解中缀表达式的过程。然后利用两个栈一个存运算符,一个存运算对象classSo......
  • LeetCode1024 -- 贪心
    1.题目描述这题题意感觉说的不是很清楚,容易让人产生歧义!其实题意很简单,给你一个链表head,你深拷贝它,然后返回即可,注意不能修改原链表/*//DefinitionforaNode.cl......
  • #yyds干货盘点# LeetCode面试题:组合总和 II
    1.简述:给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只......
  • [Leetcode Weekly Contest]334
    链接:LeetCode[Leetcode]6307.递枕头n个人站成一排,按从1到n编号。最初,排在队首的第一个人拿着一个枕头。每秒钟,拿着枕头的人会将枕头传递给队伍中的下一个人。一旦......
  • 【DFS】LeetCode 46. 全排列
    题目链接46.全排列思路本题是求排列问题.与组合问题不同的是,在排列问题中,不同的数字顺序被视为不同的排列,比如[1,2]与[2,1]是两种不同的排列。搜索树如下图所示,引......
  • LeetCode -- 只出现一次的数字
    problem11.题目描述2.思路3.代码problem21.题目描述2.思路3.代码problem31.题目描述2.思路3.代码problem41.题目描述......
  • 【DFS】LeetCode 90. 子集 II
    题目链接90.子集II思路去重方法与【DFS】LeetCode40.组合总和II思路相似代码classSolution{privateList<List<Integer>>result=newArrayList<>();......
  • 【DFS】LeetCode 78. 子集
    题目链接78.子集思路求子集问题和77.组合(opensnewwindow)和131.分割回文串(opensnewwindow)又不一样了。如果把子集问题、组合问题、分割问题都抽象为一......
  • 【DFS】LeetCode 216. 组合总和 III
    题目链接216.组合总和III思路与【DFS】LeetCode40.组合总和II思路一致,只不过candidates数组在题目中明确说明了只有1到9。代码classSolution{private......
  • #yyds干货盘点# LeetCode面试题:组合总和
    1.简述:给你一个无重复元素的整数数组 candidates和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target的所有 不同组合,并以列表形式返回。你......