资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

如何实现寻找两个正序数组的中位数

本篇内容介绍了“如何实现寻找两个正序数组的中位数”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

创新互联于2013年创立,先为长丰等服务建站,长丰等地企业,进行企业商务咨询服务。为长丰企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

题目

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

描述

难度:困难

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

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

Solution

解法

解题思路

从题目中透露的细节要求

  • 中位数

  • 两个集合

  • 两个集合均为正序集合

  • 找出这两个正序集合的中位数

什么是中位数

  • 首先需要正确理解中位数的概念,中位数是指,一个集合中,处于中间的数的数字,如果集合的长度为奇数,则为中间的数字,如果为偶数,则为中间两个数平均数

针对这道题,我们在计算中位数的时候需要区分最终的长度,最终是奇数还是偶数

合并两个正序集合

找出两个正序集合的中位数,首先第一反应想到的是合并两个正序集合,合并两个正序集合又带来新的问题,保证排序后的新集合也是正序的,否则求出来的中位数的结果是不对的

合并两个正序集合,简单粗暴的做法是,直接使用JDK现成的API合并两个数组,并且进行SORT排序,但是这样会造成时间复杂度及空间复杂度增加,所以这里我们采用常见的双指针的方式

双指针

采用三个指针指向三个数组数组的当前下标,默认从0开始,判断两个老数组的初始坐标值,小的数据则放入到新的数组中,并且更新对应的下标,如下图所示,A[0] < B[0] ,将A[0]的值赋值给CC[0]=0 ,并且将C的坐标自增,同时A的值比较小,所以A的下标自增,B坐标不动,如此循环

A的坐标,或B的坐标等于对应的数组集合长度时,说明对应的数组集合已经遍历完了,我们则可以直接拼接对应另外一个集合到新的集合中即可,直到最终两个集合拼接完成

拼接新的集合完成之后,判断最终集合的长度为奇数还是偶数,最终取出中位数,返回即可

但其实我们也可以不需要完全合并两个有序数组,只要找到中位数的位置即可,由于两个数组的长度已知,因此中位数对应的两个数组的下标之和也是已知的。在每次赋值完C之后,判断当前C下标的值是否为中位数位置,如果是可直接计算中位数的值返回即可,整理的时间复杂度也会缩短一半

这里强调一点,必须要赋值完C,因为如果先判断中位数,则C还没有赋值完,最终的结果肯定是不对的

如何实现寻找两个正序数组的中位数

CODE
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length2= nums1.length ;
        int length3= nums2.length ;
        int lengthSum = length2+length3;
        //是否偶数
        boolean type ;
        int half =0;;
        //偶数
        if(lengthSum%2 == 0){
            // half , half+1       8/2-1=4-1=3   [0,1,2,3,4,5,6,7]
            half = lengthSum/2-1;
            type= true;
        }else{
            //奇数      7/2=3
            half = lengthSum/2;
            type= false;
        }
        // num1下标
        int a = 0 ;
        // num2下标
        int b = 0 ;
        // newnums下标
        int c = 0 ;
        int[] newnums = new int[lengthSum];
        while(true){

            //a已经遍历完了
            if(a==length2){
                newnums[c] = nums2[b];
                b++;
                //半数
                if(c==half&&!type){
                    return newnums[c]/1.0;
                }
                if(c==(half+1)&&type){
                    return (newnums[c]+newnums[c-1])/2.0;
                }

                c++;
                continue ;
            }
            //b已经遍历完了
            if(b==length3){
                newnums[c] = nums1[a];
                a++;
                //半数
                if(c==half&&!type){
                    return newnums[c]/1.0;
                }
                if(c==(half+1)&&type){
                    return (newnums[c]+newnums[c-1])/2.0;
                }
                c++;
                continue ;
            }
            if(nums1[a] >= nums2[b]){
                newnums[c] = nums2[b];
                b++;
            }else{
                newnums[c] = nums1[a];
                a++;
            }
            //半数
            if(c==half&&!type){
                return newnums[c]/1.0;
            }
            if(c==(half+1)&&type){
                return (newnums[c]+newnums[c-1])/2.0;
            }
            c++;
        }
    }
}
复杂度
  • 时间复杂度:O(m+n),最长可能需要完全遍历两个数组

  • 空间复杂度:O(1)

结果
  • 执行用时:3 ms, 在所有 Java 提交中击败了82.60%的用户

    内存消耗:39.7 MB, 在所有 Java 提交中击败了63.95%的用户

我曾在银色平原漫步,也曾在青草之河垂钓,这片土地认识我,我们若不坚强,就将灭亡

“如何实现寻找两个正序数组的中位数”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!


当前标题:如何实现寻找两个正序数组的中位数
网页网址:http://www.cdkjz.cn/article/jhopcj.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220