??思維導(dǎo)圖整理大廠面試高頻數(shù)組10: 3種方法徹底解決中位數(shù)問題, 力扣4??

XanaHopper 發(fā)布于2021-09-10 10:51 / 1795人閱讀

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

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

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

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

文章目錄

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

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

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

0.導(dǎo)圖整理

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

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

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

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

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

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

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

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

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

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

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

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

2.尋找第k小數(shù) 代碼詳解

關(guān)于本題轉(zhuǎn)換為 第k小數(shù) 的思想, 就不用糾結(jié)怎么想到的了, 大家就安心的理解思想和代碼并將它記在腦中就可以了.

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

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

接下來我們來詳細解讀此思想的代碼實現(xiàn).

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

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

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

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

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

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

3.理解中位數(shù)作用進行劃分數(shù)組

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

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

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

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

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

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

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

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

源碼

Python:

# 常規(guī)思想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  # 每次循環(huán)前將 right 的值賦給 left            # A移動的條件: B遍歷到最后 或 當(dāng)前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交,判斷奇偶數(shù),更快速            return (left + right) / 2.0        else:            return right# 第k小數(shù)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),兩個數(shù)組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個            - 這樣 pivot 本身最大也只能是第 k-1 小的元素            - 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除",剩下的作為新的 nums1 數(shù)組            - 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除",剩下的作為新的 nums2 數(shù)組            - 由于我們 "刪除" 了一些元素（這些元素都比第 k 小的元素要小）,因此需要修改 k 的值,減去刪除的數(shù)的個數(shù)            """                        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)  # 第一種特殊情況,發(fā)生越界,記錄需要比較的位置                newIndex2 = min(index2 + k // 2 - 1, n - 1)  # 第一種特殊情況,發(fā)生越界,記錄需要比較的位置                pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]  # 獲取兩個需要比較的數(shù)                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:  # 可以將兩種情況合并,奇數(shù)會求兩次同樣的k            return getKthElement((totalLength + 1) // 2)        else:            return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2# 劃分數(shù)組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: # 一直循環(huán)找到一個最大的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]            # 當(dāng)一個數(shù)組不出現(xiàn)在前一部分時,對應(yīng)的值為負無窮,就不會對前一部分的最大值產(chǎn)生影響            nums_im1 = (-infinty if i == 0 else nums1[i - 1]) # 注意寫法與java不同            # 當(dāng)一個數(shù)組不出現(xiàn)在后一部分時,對應(yīng)的值為正無窮,就不會對后一部分的最小值產(chǎn)生影響            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:

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