首页 > 其他分享 >困难-4. 寻找两个正序数组的中位数

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

时间:2022-10-07 23:12:35浏览次数:53  
标签:正序 needMid ans2 中位数 mid 数组 nums1 nums2 r1

这题难了我几天,重写了几遍代码,一直感觉不对,算法复杂度没降下来,直到今天10月7日完成 ### 解题思路 不停判断区间1是否相交区间2 假如中位数存在num1中,不停地对nums1取中间值,在nums2中找,直到找到为止 假如找不到,那么最后区间1和区间2不会相交   执行结果:通过 执行用时:168 ms, 在所有 JavaScript 提交中击败了11.10%的用户 内存消耗:50.8 MB, 在所有 JavaScript 提交中击败了10.32%的用户 通过测试用例:2094 / 2094  

给定两个大小分别为 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)
链接:https://leetcode.cn/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
   //例如:求一个考生在全国的排名p,分数为num
    //先用二分法求考生在各省的排名p1、p2...pn
    //分数num在全国的排名p=p1+p2+..+pn

    //如果中位数比排名p大,以当前考生为最左边,继续上一步的查找
    //如果中位数比排名p小,以当前考生为最右边,继续上一步的查找
    //如果中位值等于排名p,那这个考生就是全国排名的中位数
    let l1=0,r1=nums1.length;
    let l2=0,r2=nums2.length;
    let isLock=true;
    let len=nums1.length+nums2.length
    const isTwo=len%2===0
    const needMid=len>>1
    let ans1
    let ans2
    while(isLock){
        console.log(l1,r1,l2,r2)
         //区间有交叉
        if(l1===r1||nums1[r1-1]<=nums2[l2]){
            isLock=false
            if(r1>needMid-l2){
                ans1=nums1[needMid-l2]
            }else{
                ans1=nums2[needMid-r1]
            }
            if(r1>needMid-1-l2){
                ans2=nums1[needMid-1-l2]
            }else{
                ans2=nums2[needMid-r1-1]
            }
            console.log(ans1,ans2)
            
        }else if(l2===r2||nums2[r2-1]<=nums1[l1]){
            isLock=false
            if(r2>needMid-l1){
                ans1=nums2[needMid-l1]
            }else{
                ans1=nums1[needMid-r2]
            }
            if(r2>needMid-1-l1){
                    ans2=nums2[needMid-l1-1]
                }else{
                    ans2=nums1[needMid-r2-1]
                }
                console.log(ans1,ans2)
        }else{
            const mid=(l1+r1)>>1
            //获取排名
            const [p1,p2]=getScope(nums1[mid],nums2,l2,r2);
            
            if(mid+p1>needMid){
                r1=mid
                r2=p1
            }else if(mid+p2<needMid){
                l1=mid
                l2=p2
            }else{
                isLock=false
                
                //在nums1中找到
                ans1=nums1[mid]
                if(needMid-mid>0&&mid>0){
                    ans2=Math.max(nums1[mid-1],nums2[needMid-mid-1])
                }else if(mid>0){
                    ans2=nums1[mid-1]
                }else{
                    ans2=nums2[needMid-mid-1]
                }
            }
        }
       
    }
    
    console.log(l1,r1,l2,r2,needMid)
    if(isTwo){
        return (ans1+ans2)/2
    }
    return ans1
    
    //获取数字在数组中的区域[左边,右边]
    function getScope(num,arr,l,r){
        let lock=true
        while(lock&&l<r){
            const m=(l+r)>>1
            if(arr[m]>num){
                r=Math.min(m,r-1);
            }else if(arr[m]<num){
                l=Math.max(m,l+1);
            }else{
                l=m;
                r=m+1;
                while(arr[l-1]===arr[m]){
                    l--
                }
                while(arr[r]===arr[m]){
                    r++
                }
                lock=false;
            }
        }
        return [l,r];
    }
    
};

 

标签:正序,needMid,ans2,中位数,mid,数组,nums1,nums2,r1
From: https://www.cnblogs.com/caoke/p/16767464.html

相关文章

  • 【C语言】初始数组
    ......
  • 攻防世界favorite_number(php数组溢出+正则m绕过+Linux命令绕过)
    <?php//php5.5.9$stuff=$_POST["stuff"];$array=['admin','user'];if($stuff===$array&&$stuff[0]!='admin'){$num=$_POST["num"];if(preg_ma......
  • P3919 【模板】可持久化线段树 1(可持久化数组)
    还是用主席树来做(因为提到不同的版本),这时候的主席树不是以权值为下标的,就是普通的线段树,维护范围1~n,i存的是a[]中的数。1#include<bits/stdc++.h>2usingnamespac......
  • C++模板类-数组
    /*Container.h所有容器的基类/*MemoryObject内存申请基类我使用TBB申请内存*/template<typenameT> classContainer:publicMemoryObject { protected: T*C......
  • 189. 轮转数组
    189.轮转数组给你一个数组,将数组中的元素向右轮转k 个位置,其中 k 是非负数。 示例1:输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮......
  • 数组的上半比分操作的优化
    对于一个二维数组进行上半部分操作求和求avg#include<cstdio>#include<iostream>#include<cmath>usingnamespacestd;constintN=1000;doublea[N][N];int......
  • Java Arrays:专为数组而生的工具类
    titleshortTitlecategorytagdescriptionheadJavaArrays:专为数组而生的工具类Arrays工具类Java核心常用工具类Java程序员进阶之路,小白的零......
  • 关于树状数组的一些思考
    在写题时看到大佬们对树状数组的精妙使用,故进一步思考树状数组中的规律和信息:存袁术数据a[], 存树状数组数据f[]1、观察到f[i]一定保存了a[i]的数据2、观察到f......
  • Java稀疏数组
    publicclassArrayDemo8{/***稀疏数组*当一个数组中大多数元素为0或同一个值,可以用稀疏数组来保存这个数组*稀疏数组的处理方式*......
  • js数组去重大全,推荐收藏
    情境:将数组vararr=[1,1,‘true’,‘true’,true,true,15,15,false,false,undefined,undefined,null,null,NaN,NaN,‘NaN’,0,0,‘a’,‘a’,{},{}];中重复的值......