如何实现寻找两个正序数组的中位数(java,leetcode,编程语言)

题目

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

描述

难度：困难

给定两个大小分别为 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

classSolution{publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2){intlength2=nums1.length;intlength3=nums2.length;intlengthSum=length2+length3;//是否偶数booleantype;inthalf=0;;//偶数if(lengthSum%2==0){//half,half+18/2-1=4-1=3[0,1,2,3,4,5,6,7]half=lengthSum/2-1;type=true;}else{//奇数7/2=3half=lengthSum/2;type=false;}//num1下标inta=0;//num2下标intb=0;//newnums下标intc=0;int[]newnums=newint[lengthSum];while(true){//a已经遍历完了if(a==length2){newnums[c]=nums2[b];b++;//半数if(c==half&&!type){returnnewnums[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){returnnewnums[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){returnnewnums[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%的用户

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