此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.

目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).

關于本專欄所有題目的目錄鏈接, 刷算法題目的順序/注意點/技巧, 以及思維導圖源文件問題請點擊此鏈接.

想進大廠, 刷算法是必不可少的, 歡迎和博主一起打卡刷力扣算法, 博主同步更新了算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!

文章目錄

• • 0.導圖整理
  • 1.常規思想的改進: 假合并/奇偶合并
  • 2.尋找第k小數 代碼詳解
  • 3.理解中位數作用進行 劃分數組
  • 源碼
  • • Python:
    • java:

題目鏈接: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

力扣上對于此題的各種思想的講解已經非常詳細了(圖文并茂), 但是他們對于自己的代碼幾乎沒什么補充, 大多都是思想講解完成直接就上代碼了, 但是本題即使思想理解了, 在代碼的理解上還是有難度的, 所以本文重點對 代碼的理解 做了詳細的解釋.

0.導圖整理

1.常規思想的改進: 假合并/奇偶合并

本題的常規思想還是挺簡單的: 使用歸并的方式, 合并兩個有序數組, 得到一個大的有序數組. 大的有序數組的中間位置的元素, 即為中位數. 但是這種思路的時間復雜度是 O(m+n), 空間復雜度是 O(m+n), 面試的時候, 面試官肯定不會滿意這樣的答案的.

因此我們必須想辦法將算法進行優化, 這里先介紹一種簡單的優化方式, 就是 假合并, 即我們并不需要真的合并兩個有序數組, 只要找到中位數的位置即可.

它的思想并不復雜, 由于兩個數組的長度已知, 因此中位數對應的兩個數組的下標之和也是已知的。維護兩個指針, 初始時分別指向兩個數組的下標0的位置, 每次將指向較小值的指針后移一位（如果一個指針已經到達數組末尾,則只需要移動另一個數組的指針）, 直到到達中位數的位置.

通過這種 假合并 的方式, 我們可以成功的將空間復雜度優化到了O(1), 但是對于時間復雜度并沒有什么優化. 講解這個方法的目的并不是為了讓大家掌握此方法, 而是為了讓大家掌握此方法的一些巧妙的 優化方式.

此方法理解是比較容易的, 但是真正寫代碼時候還是很有挑戰的, 你不僅要考慮奇偶的問題, 更要考慮 一個數組遍歷結束后 的各種邊界問題, 其實很多困難題就是難在了對于邊界的處理上面了.

此方法的一個優化點就是 將奇偶兩種情況合并到了一起, 具體思想如下:

這種思想是很有必要的, 對于數組來說, 我們經常會遇到奇偶的兩種情況處理, 如果想辦法將他們合并在一起, 那代碼寫起來就是非常順暢和整潔.

另一種合并的思想是: 我們可以在奇數的時候, 在末尾等處添加一個占位符#等, 這樣也是可以將奇數合并成偶數的情況的.

此方法的另一個優化點就是 通過在if條件中加入大量的限制條件, 從而實現了對于各種邊界問題的處理, 這也是一種很重要的思想.

此方法的時間復雜度相對于下面兩種思想還是太高了, 大家不用特意掌握此方法, 但是這兩個優化的思想還是很重要的, 要好好的理解一下.

接下來我們就來詳細講解兩個時間復雜度超低的算法代碼思想.

2.尋找第k小數 代碼詳解

關于本題轉換為 第k小數 的思想, 就不用糾結怎么想到的了, 大家就安心的理解思想和代碼并將它記在腦中就可以了.

其實關于這個算法的思想并不是太難理解, 主要就是根據兩個數的三種比較結果, 不斷地去除不滿足的元素的過程.

我認為這個思想最難的點在于 三種特殊情況的處理, 我們能否想到這三種情況, 并將他們完美的融入到代碼之中, 我感覺這才是真正的難點所在.

接下來我們來詳細解讀此思想的代碼實現.

最開始對于奇數和偶數的兩種情況進行了判斷, 其實是可以將兩種情況合并的, 只需要在奇數時求兩次同樣的k就可以了.

接下來處理了三種特殊情況中的兩種特殊情況: 一個數組為空 和 k=1.

下面的幾個定義就非常重要了, 一定要弄清這些定義的含義, 才能更輕松的理解代碼.

index1, index2作為數組的起始點的下標, 初值都是0, 但是隨著兩個數組不斷被刪除元素, 這兩個起始點也是在不斷的進行變化, 具體變化方式就是 index1 = newIndex1 + 1, 因為在刪除元素的時候 連同比較位置也一同刪去了, 所以新的開始是 比較位置 的后一位.

newindex1, newindex2作為比較點就是圖中被框中的兩個數的下標, 它的賦值過程就涉及到了 最后一個邊界情況. 因為當一個數組較短時, 其中一個比較點可能已經到達了數組的最后, 所以它的值是 兩種情況下較小的那個數.

接下來就是根據兩個比較點的大小來進行不同的操作過程了, 這里最難理解的點就是 k -= (newIndex1 - index1 + 1), 也就是減去元素的個數問題了. 我們根據上面的圖來舉例, 圖中index1的值為0, newindex1的值經過計算為1, 通過比較后, 可以看到 紅色的數 就是被刪除的數, 也就是兩個, 所以我們需要在最后+1才是真實被刪去的個數. 對于此類問題在確定最終個數的時候, 我們都可以通過這樣的特例來決定代碼的書寫, 至此代碼就全部講解完成了.

3.理解中位數作用進行 劃分數組

最后這種思想的時間復雜度甚至比上面的還低, 上面的思想每一輪循環可以將查找范圍減少一半,因此時間復雜度是O(log(m+n)), 但這種思想可以對確定的較短的數組進行二分查找, 所以它的時間復雜度是 O(log min(m,n)).

劃分數組 正好和上面算法完全相反, 它的思想特別復雜, 但思想理解了, 代碼寫起來倒是沒太大的難度, 所以我們重點說說它的思想.

首先我們要明白中位數的作用: 將一個集合劃分為兩個長度相等的子集, 其中一個子集中的元素總是大于另一個子集中的元素, 這種思想無論是在幾個數組中都是適用的, 這就衍生出了下面的算法思想.

首先來討論奇偶的兩種不同情況下的不同劃分方式.

然后在編寫代碼的時候, 由于計算機的取整操作, 我們是可以將這兩種情況合并成一種代碼書寫方式的. 其中的i和j分別是兩個數組的劃分位置.

同樣我們也會遇到復雜的邊界問題, 但下面這種處理方式是真的非常優秀.

上面問題都考慮完了, 其實就可以寫代碼了, 但是我們需要進行兩個條件的判斷: B[j?1]≤A[i] 以及A[i?1]≤B[j], 為了優化代碼, 經過分析后, 我們發現這兩種情況是可以等價轉換的. 也就是只需要進行一個條件的判斷即可.

代碼中有個注意點就是java中的三目運算符? : 在Python中是沒有引入這個符號的, 但是Python利用了已有的關鍵字if…else實現了這個功能.

源碼

Python:

# 常規思想class Solution:    def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:        m = len(A)        n = len(B)         lens = m + n        left, right = -1, -1        aStart, bStart = 0, 0        for i in range(lens//2 + 1) :            left = right  # 每次循環前將 right 的值賦給 left            # A移動的條件: B遍歷到最后 或 當前A            if aStart < m and (bStart >= n or A[aStart] < B[bStart]):                right = A[aStart]                aStart += 1            else :                right = B[bStart]                bStart += 1                    if (lens & 1) == 0: # 與1交,判斷奇偶數,更快速            return (left + right) / 2.0        else:            return right# 第k小數class Solution:    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:        def getKthElement(k):            """            - 主要思路：要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較            - 這里的 "/" 表示整除            - nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個            - nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個            - 取 pivot = min(pivot1, pivot2),兩個數組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個            - 這樣 pivot 本身最大也只能是第 k-1 小的元素            - 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除",剩下的作為新的 nums1 數組            - 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除",剩下的作為新的 nums2 數組            - 由于我們 "刪除" 了一些元素（這些元素都比第 k 小的元素要小）,因此需要修改 k 的值,減去刪除的數的個數            """                        index1, index2 = 0, 0            while True:                # 特殊情況                if index1 == m:                    return nums2[index2 + k - 1]                if index2 == n:                    return nums1[index1 + k - 1]                if k == 1:                    return min(nums1[index1], nums2[index2])                # 正常情況,index1,index2作為起始點,newindex1,newindex2作為比較點 在不停的更新                newIndex1 = min(index1 + k // 2 - 1, m - 1)  # 第一種特殊情況,發生越界,記錄需要比較的位置                newIndex2 = min(index2 + k // 2 - 1, n - 1)  # 第一種特殊情況,發生越界,記錄需要比較的位置                pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]  # 獲取兩個需要比較的數                if pivot1 <= pivot2:  # <=將兩種情況合并                    k -= newIndex1 - index1 + 1  # 兩者相減后+1,這才是真正減去的長度                    index1 = newIndex1 + 1  # 連同比較位置也一同刪去了,所以新的開始是 比較位置 的后一位                else:                    k -= newIndex2 - index2 + 1                    index2 = newIndex2 + 1                m, n = len(nums1), len(nums2)        totalLength = m + n        if totalLength % 2 == 1:  # 可以將兩種情況合并,奇數會求兩次同樣的k            return getKthElement((totalLength + 1) // 2)        else:            return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2# 劃分數組class Solution:    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:        if len(nums1) > len(nums2):            return self.findMedianSortedArrays(nums2, nums1)        infinty = 2**40  # 代表正無窮        m, n = len(nums1), len(nums2)        left, right = 0, m        # median1：前一部分的最大值        # median2：后一部分的最小值        median1, median2 = 0, 0        while left <= right: # 一直循環找到一個最大的i滿足A[i?1]≤B[j]            # 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]            # // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]            i = (left + right) // 2            j = (m + n + 1) // 2 - i            # nums_im1, nums_i, nums_jm1, nums_j 分別表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]            # 當一個數組不出現在前一部分時,對應的值為負無窮,就不會對前一部分的最大值產生影響            nums_im1 = (-infinty if i == 0 else nums1[i - 1]) # 注意寫法與java不同            # 當一個數組不出現在后一部分時,對應的值為正無窮,就不會對后一部分的最小值產生影響            nums_i = (infinty if i == m else nums1[i])            nums_jm1 = (-infinty if j == 0 else nums2[j - 1])            nums_j = (infinty if j == n else nums2[j])            if nums_im1 <= nums_j:                median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)                left = i + 1            else:                right = i - 1        return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1

java:

// 常規思想class Solution {    public double findMedianSortedArrays(int[] A, int[] B) {        int m = A.length;        int n = B.length;        int len = m + n;        int left = -1, right = -1;        int aStart = 0, bStart = 0;        for (int i = 0; i <= len / 2; i++) {            left = right;  // 每次循環前將 right 的值賦給 left            // A移動的條件: B遍歷到最后 或 當前A            if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {                right = A[aStart++];            } else {                right = B[bStart++];            }        }        if ((len & 1) == 0) // 與1交,判斷奇偶數,更快速            return (left + right) / 2.0;        else            return right;    }}// 第k小數class Solution {    public double findMedianSortedArrays(int[] nums1, int[] nums2) {        int length1 = nums1.length, length2 = nums2.length;        int totalLength = length1 + length2;        if (totalLength % 2 == 1) {  // 可以將兩種情況合并,奇數會求兩次同樣的k            int midIndex = totalLength / 2;            double median = getKthElement(nums1, nums2, midIndex + 1);            return median;        } else {            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;            return median;        }    }    public int getKthElement(int[] nums1, int[] nums2, int k) {         /* 主要思路：要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較         * 這里的 "/" 表示整除         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個         * 取 pivot = min(pivot1, pivot2),兩個數組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個         * 這樣 pivot 本身最大也只能是第k-1小的元素         * 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除",剩下的作為新的 nums1 數組         * 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除",剩下的作為新的 nums2 數組         * 由于我們 "刪除" 了一些元素（這些元素都比第 k 小的元素要小）,因此需要修改 k 的值,減去刪除的數的個數         */        int length1 = nums1.length, length2 = nums2.length;        int index1 = 0, index2 = 0;        int kthElement = 0;        while (true) {            // 特殊情況            if (index1 == length1) {  // 第二種特殊情況,一個數組為空                return nums2[index2 + k - 1];            }            if (index2 == length2) {  // 第二種特殊情況,一個數組為空                return nums1[index1 + k - 1];            }            if (k == 1) {             // 第三種特殊情況,k=1                return Math.min(nums1[index1], nums2[index2]);            }                        // 正常情況,index1,index2作為起始點,newindex1,newindex2作為比較點 在不停的更新            int half = k / 2;            int newIndex1 = Math.min(index1 + half, length1) - 1; //第一種特殊情況,發生越界,記錄需要比較的位置            int newIndex2 = Math.min(index2 + half, length2) - 1;  //第一種特殊情況,發生越界,記錄需要比較的位置            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];  //獲取兩個需要比較的數            if (pivot1 <= pivot2) {  // <=將兩種情況合并                k -= (newIndex1 - index1 + 1); //兩者相減后+1,這才是真正減去的長度                index1 = newIndex1 + 1;  //連同比較位置也一同刪去了,所以新的開始是 比較位置 的后一位            } else {                k -= (newIndex2 - index2 + 1);                index2 = newIndex2 + 1;            }        }    }}// 劃分數組class Solution {    public double findMedianSortedArrays(int[] nums1, int[] nums2) {        if (nums1.length > nums2.length) {            return findMedianSortedArrays(nums2, nums1);        }        int m = nums1.length;        int n = nums2.length;        int left = 0, right = m;        // median1：前一部分的最大值        // median2：后一部分的最小值        int median1 = 0, median2 = 0;        while (left <= right) { // 一直循環找到一個最大的i滿足A[i-1]≤B[j]            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]            int i = (left + right) / 2; //二分法,i從區間中間開始            int j = (m + n + 1) / 2 - i;//+1的操作將總數為奇數和偶數合并為一種情況            //nums_im1, nums_i, nums_jm1, nums_j 分別表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]            //當一個數組不出現在前一部分時,對應的值為負無窮,就不會對前一部分的最大值產生影響            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);            //當一個數組不出現在后一部分時,對應的值為正無窮,就不會對后一部分的最小值產生影響            int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);            int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);            if (nums_im1 <= nums_j) {                median1 = Math.max(nums_im1, nums_jm1);                median2 = Math.min(nums_i, nums_j);                left = i + 1;            }            else {                right = i - 1;            }        }        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;    }}

我的更多精彩文章鏈接, 歡迎查看

各種電腦/軟件/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)

力扣算法刷題 根據思維導圖整理筆記快速記憶算法重點內容(歡迎和博主一起打卡刷題哦)

計算機專業知識 思維導圖整理

最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/數據結構/常見錯誤/經典思想(持續更新中)

最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟件工程初試906科目

最值得收藏的 計算機網絡 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介

最值得收藏的 算法分析與設計 全部知識點思維導圖整理(北大慕課課程)

最值得收藏的 數據結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理

最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)

最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)

最值得收藏的 數字圖像處理 全部知識點思維導圖整理(武漢大學慕課課程)

紅黑樹 一張導圖解決紅黑樹全部插入和刪除問題 包含詳細操作原理 情況對比

各種常見排序算法的時間/空間復雜度 是否穩定 算法選取的情況 改進 思維導圖整理

人工智能課件 算法分析課件 Python課件 數值分析課件 機器學習課件 圖像處理課件

考研相關科目 知識點 思維導圖整理

考研經驗–東南大學軟件學院軟件工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)

東南大學 軟件工程 906 數據結構 C++ 歷年真題 思維導圖整理

東南大學 軟件工程 復試3門科目歷年真題 思維導圖整理

最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理

最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理

高等數學 中值定理 一