189 8069 5689
本篇内容介绍了“如何实现寻找两个正序数组的中位数”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
创新互联于2013年创立，先为长丰等服务建站，长丰等地企业，进行企业商务咨询服务。为长丰企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
难度：困难
给定两个大小分别为 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 == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106
从题目中透露的细节要求
中位数
两个集合
两个集合均为正序集合
找出这两个正序集合的中位数
什么是中位数
首先需要正确理解中位数的概念，中位数是指，一个集合中，处于中间的数的数字，如果集合的长度为奇数，则为中间的数字，如果为偶数，则为中间两个数的平均数
针对这道题，我们在计算中位数的时候需要区分最终的长度，最终是奇数还是偶数
合并两个正序集合
找出两个正序集合的中位数，首先第一反应想到的是合并两个正序集合，合并两个正序集合又带来新的问题，保证排序后的新集合也是正序的，否则求出来的中位数的结果是不对的
合并两个正序集合，简单粗暴的做法是，直接使用JDK现成的API合并两个数组，并且进行SORT排序，但是这样会造成时间复杂度及空间复杂度增加，所以这里我们采用常见的双指针的方式
双指针
采用三个指针指向三个数组数组的当前下标，默认从0开始，判断两个老数组的初始坐标值，小的数据则放入到新的数组中，并且更新对应的下标，如下图所示，A[0] < B[0] ，将A[0]的值赋值给C，C[0]=0 ,并且将C的坐标自增，同时A的值比较小，所以A的下标自增，B坐标不动，如此循环
当A的坐标，或B的坐标等于对应的数组集合长度时，说明对应的数组集合已经遍历完了，我们则可以直接拼接对应另外一个集合到新的集合中即可，直到最终两个集合拼接完成
拼接新的集合完成之后，判断最终集合的长度为奇数还是偶数，最终取出中位数，返回即可
但其实我们也可以不需要完全合并两个有序数组，只要找到中位数的位置即可，由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。在每次赋值完C之后，判断当前C下标的值是否为中位数位置，如果是可直接计算中位数的值返回即可，整理的时间复杂度也会缩短一半
这里强调一点，必须要赋值完C，因为如果先判断中位数，则C还没有赋值完，最终的结果肯定是不对的
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%的用户
我曾在银色平原漫步,也曾在青草之河垂钓，这片土地认识我，我们若不坚强，就将灭亡
“如何实现寻找两个正序数组的中位数”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！