如何實現(xiàn)尋找兩個正序數(shù)組的中位數(shù)

本篇內(nèi)容介紹了“如何實現(xiàn)尋找兩個正序數(shù)組的中位數(shù)”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

題目

尋找兩個正序數(shù)組的中位數(shù)

描述

難度：困難

給定兩個大小分別為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請你找出并返回這兩個正序數(shù)組的 中位數(shù) 。

示例 1：

輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數(shù)組 = [1,2,3] ，中位數(shù) 2

示例 2：

輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數(shù)組 = [1,2,3,4] ，中位數(shù) (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

解法

解題思路

從題目中透露的細(xì)節(jié)要求

• 中位數(shù)

• 兩個集合

• 兩個集合均為正序集合

• 找出這兩個正序集合的中位數(shù)

什么是中位數(shù)

• 首先需要正確理解中位數(shù)的概念，中位數(shù)是指，一個集合中，處于中間的數(shù)的數(shù)字，如果集合的長度為奇數(shù)，則為中間的數(shù)字，如果為偶數(shù)，則為中間兩個數(shù)的平均數(shù)

針對這道題，我們在計算中位數(shù)的時候需要區(qū)分最終的長度，最終是奇數(shù)還是偶數(shù)

合并兩個正序集合

找出兩個正序集合的中位數(shù)，首先第一反應(yīng)想到的是合并兩個正序集合，合并兩個正序集合又帶來新的問題，保證排序后的新集合也是正序的，否則求出來的中位數(shù)的結(jié)果是不對的

合并兩個正序集合，簡單粗暴的做法是，直接使用JDK現(xiàn)成的API合并兩個數(shù)組，并且進行SORT排序，但是這樣會造成時間復(fù)雜度及空間復(fù)雜度增加，所以這里我們采用常見的雙指針的方式

雙指針

采用三個指針指向三個數(shù)組數(shù)組的當(dāng)前下標(biāo)，默認(rèn)從0開始，判斷兩個老數(shù)組的初始坐標(biāo)值，小的數(shù)據(jù)則放入到新的數(shù)組中，并且更新對應(yīng)的下標(biāo)，如下圖所示，A[0] < B[0] ，將A[0]的值賦值給C，C[0]=0 ,并且將C的坐標(biāo)自增，同時A的值比較小，所以A的下標(biāo)自增，B坐標(biāo)不動，如此循環(huán)

當(dāng)A的坐標(biāo)，或B的坐標(biāo)等于對應(yīng)的數(shù)組集合長度時，說明對應(yīng)的數(shù)組集合已經(jīng)遍歷完了，我們則可以直接拼接對應(yīng)另外一個集合到新的集合中即可，直到最終兩個集合拼接完成

拼接新的集合完成之后，判斷最終集合的長度為奇數(shù)還是偶數(shù)，最終取出中位數(shù)，返回即可

但其實我們也可以不需要完全合并兩個有序數(shù)組，只要找到中位數(shù)的位置即可，由于兩個數(shù)組的長度已知，因此中位數(shù)對應(yīng)的兩個數(shù)組的下標(biāo)之和也是已知的。在每次賦值完C之后，判斷當(dāng)前C下標(biāo)的值是否為中位數(shù)位置，如果是可直接計算中位數(shù)的值返回即可，整理的時間復(fù)雜度也會縮短一半

這里強調(diào)一點，必須要賦值完C，因為如果先判斷中位數(shù)，則C還沒有賦值完，最終的結(jié)果肯定是不對的

CODE

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length2= nums1.length ;
        int length3= nums2.length ;
        int lengthSum = length2+length3;
        //是否偶數(shù)
        boolean type ;
        int half =0;;
        //偶數(shù)
        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{
            //奇數(shù)      7/2=3
            half = lengthSum/2;
            type= false;
        }
        // num1下標(biāo)
        int a = 0 ;
        // num2下標(biāo)
        int b = 0 ;
        // newnums下標(biāo)
        int c = 0 ;
        int[] newnums = new int[lengthSum];
        while(true){

            //a已經(jīng)遍歷完了
            if(a==length2){
                newnums[c] = nums2[b];
                b++;
                //半數(shù)
                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已經(jīng)遍歷完了
            if(b==length3){
                newnums[c] = nums1[a];
                a++;
                //半數(shù)
                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++;
            }
            //半數(shù)
            if(c==half&&!type){
                return newnums[c]/1.0;
            }
            if(c==(half+1)&&type){
                return (newnums[c]+newnums[c-1])/2.0;
            }
            c++;
        }
    }
}

復(fù)雜度

• 時間復(fù)雜度：O(m+n)，最長可能需要完全遍歷兩個數(shù)組

• 空間復(fù)雜度：O(1)

結(jié)果

• 執(zhí)行用時：3 ms, 在所有 Java 提交中擊敗了82.60%的用戶

  內(nèi)存消耗：39.7 MB, 在所有 Java 提交中擊敗了63.95%的用戶

我曾在銀色平原漫步,也曾在青草之河垂釣，這片土地認(rèn)識我，我們?nèi)舨粓詮?，就將滅?/p>

“如何實現(xiàn)尋找兩個正序數(shù)組的中位數(shù)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！