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

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

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

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

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

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

文章目錄

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

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

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

0.導(dǎo)圖整理

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

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

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

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

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

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

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

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

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

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

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

接下來(lái)我們就來(lái)詳細(xì)講解兩個(gè)時(shí)間復(fù)雜度超低的算法代碼思想.

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

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

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

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

接下來(lái)我們來(lái)詳細(xì)解讀此思想的代碼實(shí)現(xiàn).

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

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

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

index1, index2作為數(shù)組的起始點(diǎn)的下標(biāo), 初值都是0, 但是隨著兩個(gè)數(shù)組不斷被刪除元素, 這兩個(gè)起始點(diǎn)也是在不斷的進(jìn)行變化, 具體變化方式就是 index1 = newIndex1 + 1, 因?yàn)樵趧h除元素的時(shí)候 連同比較位置也一同刪去了, 所以新的開(kāi)始是比較位置的后一位.

newindex1, newindex2作為比較點(diǎn)就是圖中被框中的兩個(gè)數(shù)的下標(biāo), 它的賦值過(guò)程就涉及到了 最后一個(gè)邊界情況. 因?yàn)楫?dāng)一個(gè)數(shù)組較短時(shí), 其中一個(gè)比較點(diǎn)可能已經(jīng)到達(dá)了數(shù)組的最后, 所以它的值是 兩種情況下較小的那個(gè)數(shù).

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

3.理解中位數(shù)作用進(jìn)行劃分?jǐn)?shù)組

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

劃分?jǐn)?shù)組正好和上面算法完全相反, 它的思想特別復(fù)雜, 但思想理解了, 代碼寫(xiě)起來(lái)倒是沒(méi)太大的難度, 所以我們重點(diǎn)說(shuō)說(shuō)它的思想.

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

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

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

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

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

代碼中有個(gè)注意點(diǎn)就是java中的三目運(yùn)算符? : 在Python中是沒(méi)有引入這個(gè)符號(hào)的, 但是Python利用了已有的關(guān)鍵字if…else實(shí)現(xiàn)了這個(gè)功能.

源碼

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移動(dòng)的條件: 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] 進(jìn)行比較            - 這里的 "/" 表示整除            - nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計(jì) k/2-1 個(gè)            - nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計(jì) k/2-1 個(gè)            - 取 pivot = min(pivot1, pivot2),兩個(gè)數(shù)組中小于等于 pivot 的元素共計(jì)不會(huì)超過(guò) (k/2-1) + (k/2-1) <= k-2 個(gè)            - 這樣 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ù)的個(gè)數(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作為起始點(diǎn),newindex1,newindex2作為比較點(diǎn) 在不停的更新                newIndex1 = min(index1 + k // 2 - 1, m - 1)  # 第一種特殊情況,發(fā)生越界,記錄需要比較的位置                newIndex2 = min(index2 + k // 2 - 1, n - 1)  # 第一種特殊情況,發(fā)生越界,記錄需要比較的位置                pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]  # 獲取兩個(gè)需要比較的數(shù)                if pivot1 <= pivot2:  # <=將兩種情況合并                    k -= newIndex1 - index1 + 1  # 兩者相減后+1,這才是真正減去的長(zhǎng)度                    index1 = newIndex1 + 1  # 連同比較位置也一同刪去了,所以新的開(kāi)始是 比較位置 的后一位                else:                    k -= newIndex2 - index2 + 1                    index2 = newIndex2 + 1                m, n = len(nums1), len(nums2)        totalLength = m + n        if totalLength % 2 == 1:  # 可以將兩種情況合并,奇數(shù)會(huì)求兩次同樣的k            return getKthElement((totalLength + 1) // 2)        else:            return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2# 劃分?jǐn)?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  # 代表正無(wú)窮        m, n = len(nums1), len(nums2)        left, right = 0, m        # median1：前一部分的最大值        # median2：后一部分的最小值        median1, median2 = 0, 0        while left <= right: # 一直循環(huán)找到一個(gè)最大的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)一個(gè)數(shù)組不出現(xiàn)在前一部分時(shí),對(duì)應(yīng)的值為負(fù)無(wú)窮,就不會(huì)對(duì)前一部分的最大值產(chǎn)生影響            nums_im1 = (-infinty if i == 0 else nums1[i - 1]) # 注意寫(xiě)法與java不同            # 當(dāng)一個(gè)數(shù)組不出現(xiàn)在后一部分時(shí),對(duì)應(yīng)的值為正無(wú)窮,就不會(huì)對(duì)后一部分的最小值產(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移動(dòng)的條件: 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ù)會(huì)求兩次同樣的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] 進(jìn)行比較         * 這里的 "/" 表示整除         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計(jì) k/2-1 個(gè)         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計(jì) k/2-1 個(gè)         * 取 pivot = min(pivot1, pivot2),兩個(gè)數(shù)組中小于等于 pivot 的元素共計(jì)不會(huì)超過(guò) (k/2-1) + (k/2-1) <= k-2 個(gè)         * 這樣 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ù)的個(gè)數(shù)         */        int length1 = nums1.length, length2 = nums2.length;        int index1 = 0, index2 = 0;        int kthElement = 0;        while (true) {            // 特殊情況            if (index1 == length1) {  // 第二種特殊情況,一個(gè)數(shù)組為空                return nums2[index2 + k - 1];            }            if (index2 == length2) {  // 第二種特殊情況,一個(gè)數(shù)組為空                return nums1[index1 + k - 1];            }            if (k == 1) {             // 第三種特殊情況,k=1                return Math.min(nums1[index1], nums2[index2]);            }                        // 正常情況,index1,index2作為起始點(diǎn),newindex1,newindex2作為比較點(diǎn) 在不停的更新            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];  //獲取兩個(gè)需要比較的數(shù)            if (pivot1 <= pivot2) {  // <=將兩種情況合并                k -= (newIndex1 - index1 + 1); //兩者相減后+1,這才是真正減去的長(zhǎng)度                index1 = newIndex1 + 1;  //連同比較位置也一同刪去了,所以新的開(kāi)始是 比較位置 的后一位            } else {                k -= (newIndex2 - index2 + 1);                index2 = newIndex2 + 1;            }        }    }}// 劃分?jǐn)?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)找到一個(gè)最大的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ū)間中間開(kāi)始            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)一個(gè)數(shù)組不出現(xiàn)在前一部分時(shí),對(duì)應(yīng)的值為負(fù)無(wú)窮,就不會(huì)對(duì)前一部分的最大值產(chǎn)生影響            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);            //當(dāng)一個(gè)數(shù)組不出現(xiàn)在后一部分時(shí),對(duì)應(yīng)的值為正無(wú)窮,就不會(huì)對(duì)后一部分的最小值產(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;    }}