导航：首页 > 开发技术 >

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

发表于：2024-11-11 作者：千家信息网编辑

千家信息网最后更新 2024年11月11日，本篇内容介绍了"如何实现寻找两个正序数组的中位数"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！题目寻

千家信息网最后更新 2024年11月11日如何实现寻找两个正序数组的中位数

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

题目

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

描述

难度：困难

给定两个大小分别为 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 == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106

Solution

解法

解题思路

从题目中透露的细节要求

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

什么是中位数

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

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

合并两个正序集合

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

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

双指针

采用三个指针指向三个数组数组的当前下标，默认从0开始，判断两个老数组的初始坐标值，小的数据则放入到新的数组中，并且更新对应的下标，如下图所示，A[0] < B[0] ，将A[0]的值赋值给C，C[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++;        }    }}