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

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

题目

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

描述

难度：困难

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

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++;
        }
    }
}

复杂度

• 时间复杂度：O(m+n)，最长可能需要完全遍历两个数组

• 空间复杂度：O(1)

结果

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

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

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

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