題目描述

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

進階：你能設(shè)計一個時間復(fù)雜度為 O(log(m + n)) 的算法解決此問題嗎？

提示：
? 0 <= m、n <= 1000
? m+n >= 1
? -10⁶ <= nums1[i] 、nums2[i] <= 10⁶

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

輸入：nums1 = [1, 2]，nums2 = [3, 4]
輸出：2.5
解釋：合并數(shù)組=[1,2,3,4]，因此中位數(shù)是 (2 + 3)/2 = 2.5

數(shù)據(jù)結(jié)構(gòu)

• 數(shù)組

算法思維

• 歸并排序、二分查找

關(guān)鍵知識點：歸并排序（Merge Sort）

• 將序列拆成兩個或兩個以上分別排序，然后再合并成一個
  采用分治思想，基于歸并操作的一種穩(wěn)定排序算法
  穩(wěn)定排序：對于關(guān)鍵字相等的元素在排序前后相對順序保持不變

• 歸并排序原理
  尋找兩個有序數(shù)組的最小值，即兩個數(shù)組最小值中較小的那個，放入合并后數(shù)組的第一位
  尋找兩個數(shù)組第2小的值
  尋找兩個數(shù)組第3小的值
  ......
  依次進行直到結(jié)束

  
  

? 首先將數(shù)組拆分成兩部分
? 對這兩部分分別遞歸排序
? 元素個數(shù)大于1，繼續(xù)拆分
? 只有一個元素時無需排序，結(jié)束遞歸
? 在對有序數(shù)組進行兩兩合并

class Solution{
    public static int[] mergeSort(int[] arr) {
        if (arr.length < 2) return arr;
        //計算中間位置
        int mid = arr.length / 2;
        //分解為左右兩部分,分別排序
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        left = mergeSort(left);
        int[] right=Arrays.copyOfRange(arr,mid,arr.length);
        right = mergeSort(right);
        //合并兩個排序后的數(shù)組為一個數(shù)組
        return merge(left, right);
    }

    private static int[] merge(int[] l, int[] r) {
        int[] result = new int[l.length + r.length];
        int lIndex = 0;
        int rIndex = 0;
        for (int i = 0; i < result.length; i++) {
            if (lIndex < l.length && rIndex < r.length) {
                if (l[lIndex] <= r[rIndex]) {
                    result[i] = l[lIndex++];
                } else {
                    result[i] = r[rIndex++];
                }
            } else if (lIndex >= l.length) {
                result[i] = r[rIndex++];
            } else {
                result[i] = l[lIndex++];
            }
        }
        return result;
    }
}

時間復(fù)雜度：O(nlogn)
? ? 需要遞歸的將數(shù)組切割 logn 次，然后進行兩兩歸并，時間復(fù)雜度為 O(nlogn)

空間復(fù)雜度：O(n)
? ? 遞歸深度是 O(logn)
? ? 每次遞歸在合并時需額外輔助空間，長度與待排序的數(shù)組長度相等
? ? 每次遞歸都會釋放掉所占的輔助空間，最大輔助空間為 O(n)
? ? 所以空間復(fù)雜度為 O(n+logn) = O(n)

關(guān)鍵知識點：二分查找（折半查找）

使用折半的方式在有序數(shù)組中查找某一特定元素

• 從數(shù)組的中間元素開始查找，如果中間元素等于目標元素，查找結(jié)束；
• 如果中間元素小于目標元素，則在右半部分繼續(xù)查找；
• 如果中間元素大于目標元素，則在左半部分繼續(xù)查找；
• 如果在某一步驟數(shù)組為空，則代表找不到，查找結(jié)束；

每一次比較都使查找范圍縮小一半

//二分查找算法，在a[start] ~ a[end]中查找key
public int binarySearch(int key, int a[], int start, int end) {
    if (start > end) //未找到key，返回-1
        return -1;

    int m = (start + end) / 2;
    if (a[m] == key) //找到key，返回key的id
        return m;
    if (a[m] > key)
        return binarySearch(key, a, start, m - 1);//在m左側(cè)繼續(xù)查找
    
    return binarySearch(key, a, m + 1, end);//在m右側(cè)繼續(xù)查找
}

解題步驟

一. Comprehend 理解題意

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

• 兩個數(shù)組都是正序數(shù)組
• 尋找兩個數(shù)組所有元素的中位數(shù)

進階要求

• 算法的時間復(fù)雜度為 O(log(m+n))

寬松限制

• m + n >= 1：數(shù)組不同時為空（中位數(shù)一定存在）

細節(jié)問題

• 某個數(shù)組可能為空
• 元素總數(shù)為偶數(shù)時，中位數(shù)是中間兩數(shù)平均值（不一定是整數(shù)）
  
  

二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)選擇

• 輸入的數(shù)據(jù)類型為兩個整形數(shù)組
• 輸出的數(shù)據(jù)類型為一個浮點數(shù)
• 因為需要處理的是兩個有序的整數(shù)集合，我們采用數(shù)組作為數(shù)據(jù)結(jié)構(gòu)

算法思維選擇

• 題目要求尋找中位數(shù)，我們可以對兩個數(shù)組進行合并和排序
• 在排序后的數(shù)組中我們可以很容易地找到中位數(shù)
• 有沒有更好的合并、排序方案? -- 歸并排序
  解題思路
  ? 題目中給定兩個有序數(shù)組
  ? 直接使用歸并排序的最后一步對兩個數(shù)組進行合并即可
  時間復(fù)雜度
  ? 需要對兩個數(shù)組各瀏覽一遍，進行 m+n-1 次比較，時間復(fù)雜度為 O(m+n)
  空間復(fù)雜度
  ? 需要額外的空間存儲合并排序后的數(shù)組，空間復(fù)雜度為 O(m+n)

算法思維優(yōu)化

• 題目要求尋找中位數(shù)，其實我們并不需要得到合并后的有序數(shù)組
• 歸并排序進行到一半的時候，我們其實已經(jīng)找到了中位數(shù)
• 算法可以被改進為遍歷兩個有序數(shù)組 num1 和 nums2：
  ? 若 |nums1|+|nums2| 為奇數(shù)，尋找第 (|nums1|+|nums2|+1)/2 小的數(shù)
  ? 若 |nums1|+|nums2| 為偶數(shù)，尋找第 (|nums1|+|nums2|)/2 和 (|nums1|+|nums2|+2)/2 小的數(shù)
  
  

三. Code 編碼實現(xiàn)基本解法

解題思路剖析

• 遍歷有序數(shù)組 nums1 和 nums2，尋找中位數(shù)
• 使用歸并排序的思想，但是并不真正構(gòu)建歸并后的數(shù)組
• 遍歷有序數(shù)組nums1和nums2，尋找中位數(shù)
• |nums1|+|nums2|= 4+3 = 7, 中位數(shù)為第 (7+1)/2=4 小的數(shù)

代碼實現(xiàn)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        
        //定義指針p1,p2 分別指代nums1和nums2的當前元素
        int p1 = 0, p2 = 0;
        //定義中位數(shù)m1和m2，指代當前第i-1大的數(shù)和第i大的數(shù)
        int m1 = 0, m2 = 0;
        
        for (int i = 0; i <= (m + n) / 2; i++) {
            m1 = m2; //指針右移
            //若nums1未處理完，并且 nums2已處理完 或 p1元素小于p2元素
            //則第i大的元素為nums1當前元素
            if (p1 < m && (p2 >= n || nums1[p1] < nums2[p2])) {
                m2 = nums1[p1++];
            } else { //否則第i大的元素為nums2當前元素
                m2 = nums2[p2++];
            } 
        }

        //若m+n為奇數(shù)，返回m2，若m+n為偶數(shù)，返回(m1+m2)/2.0
        if (((m + n) % 2) == 0) return (m1 + m2) / 2.0;
        else return m2;
    }
}

時間復(fù)雜度：O(m+n)
? ? 需要多次比較兩個數(shù)組中元素的大小
? ? 只需要找到中間位置的元素，并不需要完成整個歸并，總的比較次數(shù)為 (m+n)/2 + 1
? ? 時間復(fù)雜度為 O(m+n)

空間復(fù)雜度：O(1)
? ? 常數(shù)級的變量空間 O(1)

執(zhí)行耗時：3 ms，擊敗了 69.10% 的Java用戶
內(nèi)存消耗：41 MB，擊敗了 24.82% 的Java用戶

四. Consider 思考更優(yōu)解

剔除無效代碼 優(yōu)化空間消耗

尋找更好的算法思維

• 當前瀏覽了輸入 nums1 和 nums2 總數(shù)據(jù)的一半
• 有沒有可能瀏覽更少的元素就可以確定中位數(shù)？

中位數(shù)的性質(zhì)

• 中位數(shù)可以將數(shù)組分成 2 份
  ? 小于等于中位數(shù)的元素
  ? 大于中位數(shù)的元素
  這兩個數(shù)組的元素個數(shù)之差小于等于 1
• 尋找中位數(shù)的問題 變?yōu)?尋找滿足下列條件的分界線：
  1）分界線左邊的元素都小于等于分界線右邊的元素
  2）0 <= 分界線左邊的元素個數(shù) - 分界線右邊的元素個數(shù) <= 1
• 如何查找分界線？ -- 二分查找
  
  

五. Code 編碼實現(xiàn)最優(yōu)解

解題思路剖析

• 找到 nums1 和 nums2 的分界線，將所有元素劃分為兩部分，使得：
  分界線左邊的元素都小于等于分界線右邊的元素
  0 <= 分界線左邊的元素個數(shù)-分界線右邊的元素個數(shù) <= 1
• 在 nums1 和 nums2 中元素較少的數(shù)組進行二分查找分界線
• 若 |nums1|+|nums2| 為奇數(shù)，返回分界線左側(cè)元素的最大值
• 若 |nums1|+|nums2| 為偶數(shù)，返回分界線左側(cè)元素最大值與右側(cè)元素最小值的平均

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        //較短的數(shù)組在前，確保m <= n
        if (m > n) return findMedianSortedArrays(nums2, nums1);

        //定義p、q為nums1分界線范圍，共m+1個可能的劃分位置
        int p = 0, q = m;
        int i = 0, j = 0; //nums1、num2的分界位置

        //使用循環(huán)代替遞歸，減少空間消耗
        while (p <= q) {
            i = (p + q) / 2; //二分確定nums1當前分界位置
            //根據(jù)i確定nums2的分界位置，使得左側(cè)元素數(shù)-右側(cè)元素數(shù)為0或1
            j = (m + n + 1) / 2 - i;
            //nums1右側(cè)最小值小于nums2左側(cè)最大值，nums1劃分位置在[i+1, q]之間
            if (j != 0 && i != m && nums1[i] < nums2[j - 1]) p = i + 1;
            //nums1左側(cè)最大值大于nums2右側(cè)最小值，nums1劃分位置在[p, i-1]之間
            else if (i != 0 && j != n && nums1[i - 1] > nums2[j]) q = i - 1;
            //當前劃分位置左側(cè)的最大值小于右側(cè)的最小值，滿足要求
            else break;
        }

        //m+n為奇數(shù)，返回左側(cè)的最大值 左側(cè)最大值：三種情況 nums1為空、nums2為空、都不為空
        int maxLeft = i == 0 ? nums2[j - 1] : (j == 0 ? nums1[i - 1] : Math.max(nums1[i - 1], nums2[j - 1]));
        if ((m + n) % 2 == 1) return maxLeft;

        //m+n為偶數(shù)，返回左側(cè)最大值與右側(cè)最小值的平均 右側(cè)最小值：三種情況 nums1為空、nums2為空、都不為空
        int minRight = i == m ? nums2[j] : (j == n ? nums1[i] : Math.min(nums1[i], nums2[j]));
        return (maxLeft + minRight) / 2.0;
    }
}

時間復(fù)雜度：O(log(min(m,n)))
? ? 只需要對 nums1 和 nums2 中較短數(shù)組進行二分查找
? ? 二分查找的時間復(fù)雜度為 O(log(min(m,n)))

空間復(fù)雜度：O(1)
? ? 常數(shù)級內(nèi)存空間 O(1)

執(zhí)行耗時：2 ms，擊敗了 100.00% 的Java用戶
內(nèi)存消耗：40.9 MB，擊敗了 35.53% 的Java用戶

六. Change 變形與延伸

題目變形

• （練習）如果輸入 nums1 和 nums2 變?yōu)槟嫘驍?shù)組該如何實現(xiàn)？

延伸擴展

• 二分查找是一種基礎(chǔ)高效的算法思維
• 實際工作中應(yīng)用非常廣泛
  數(shù)據(jù)庫中使用最頻繁的查找算法 select * from tb where dt = 2021-01-30
  數(shù)學方程求根