思維導(dǎo)圖整理大廠面試高頻數(shù)組24: 合并兩個(gè)有序數(shù)組的兩種雙指針?biāo)枷? 力扣88

darkerXi 發(fā)布于2021-11-17 09:33 / 3272人閱讀

摘要：此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn)當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解目的是為了更方便快捷的記憶和回憶算法重點(diǎn)不用每次都重復(fù)看題解畢竟算法不是做了一遍就能完全記住的所

此專欄文章是對(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)圖源文件問題請(qǐng)點(diǎn)擊此鏈接.

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

關(guān)注博主獲得題解更新的最新消息!!!

文章目錄

0.導(dǎo)圖整理
1.直接合并后排序
2.常規(guī)雙指針
3.逆向雙指針
4.進(jìn)階: 合并并去重
源碼
Python:
java:

題目鏈接: https://leetcode-cn.com/problems/merge-sorted-array/solution/si-wei-dao-tu-zheng-li-liang-chong-shuan-iahh/

0.導(dǎo)圖整理

1.直接合并后排序

這是最容易想到的方法: 先將數(shù)組nums2放進(jìn)數(shù)組nums1的尾部, 然后直接對(duì)整個(gè)數(shù)組進(jìn)行排序. 實(shí)現(xiàn)起來(lái)也是非常簡(jiǎn)單的, 但時(shí)間復(fù)雜度和空間復(fù)雜度都很高, 畢竟用到了排序算法, 建議面試時(shí)候千萬(wàn)別寫這種題解, 不然可能直接就回去等通知了!

2.常規(guī)雙指針

方法一沒有利用數(shù)組nums1與nums2已經(jīng)被排序的性質(zhì), 為了利用這一性質(zhì), 可以使用雙指針方法, 將兩個(gè)數(shù)組看作隊(duì)列, 每次從兩個(gè)數(shù)組頭部取出比較小的數(shù)字放到結(jié)果中, 這時(shí)有個(gè)注意點(diǎn): 必須當(dāng)兩個(gè)數(shù)組的指針都到達(dá)尾部時(shí), 算法才算結(jié)束, 這點(diǎn)和下面的方法還是有點(diǎn)區(qū)別的, 需要注意一下.

最后一個(gè)小的注意點(diǎn)就是在python中的語(yǔ)法: nums1[:] = sorted, 它表示對(duì)nums1從頭到尾切片, 然后進(jìn)行一一賦值, 相當(dāng)于進(jìn)行了深拷貝.

3.逆向雙指針

方法二中, 之所以要使用臨時(shí)數(shù)組變量, 是因?yàn)槿绻?strong>直接合并到數(shù)組nums1中, nums1中的元素可能會(huì)在取出之前被覆蓋.

觀察可知, nums1的后半部分是空的, 可以直接覆蓋而不會(huì)影響結(jié)果, 所以可以將指針設(shè)置為從后向前遍歷, 每次取兩者之中的較大者放進(jìn)nums1的最后面, 這樣就完美的解決了被覆蓋的問題. 下面是合理性的證明, 感興趣的可以看一下.

嚴(yán)格來(lái)說，在此遍歷過程中的任意一個(gè)時(shí)刻，nums1數(shù)組中有m?p1?1個(gè)元素被放入nums1的后半部，nums2數(shù)組中有n?p2?1個(gè)元素被放入nums1的后半部，而在指針p1的后面，nums1數(shù)組有m+n?p1?1個(gè)位置。由于m+n?p1 ?1≥m?p1 ?1+n?p2 ?1 等價(jià)于 p2≥?1永遠(yuǎn)成立，因此p1后面的位置永遠(yuǎn)足夠容納被插入的元素，不會(huì)產(chǎn)生p1的元素被覆蓋的情況

最后有個(gè)注意點(diǎn), 之前我們說到方法二終止的條件是: 兩個(gè)指針都遍歷到了數(shù)組結(jié)尾, 但是在這種方法中, 并不需要兩個(gè)指針都遍歷到開頭, 只需要nums2空了, 遍歷就結(jié)束了, 不用考慮nums1, 因?yàn)榇藭r(shí)nums1中剩下的元素都是小于nums2的最小元素的, 且它們的順序本來(lái)就是排好的, 所以在代碼上相較于方法二有了一些簡(jiǎn)化的操作. 具體可以看兩者代碼的不同.

4.進(jìn)階: 合并并去重

這是在面試中可能會(huì)被問到的進(jìn)階問題, 解決的方法是: 在方法三的基礎(chǔ)上, 因?yàn)槭怯行虻? 每次比較完兩個(gè)值后判斷前一個(gè)放進(jìn)數(shù)組里的值是不是和這次將要放進(jìn)數(shù)組的值相等就行了, 如果相等的話這一步比較出來(lái)的值就不放進(jìn)數(shù)組.

但其實(shí)這樣還是有點(diǎn)問題的: 如果是從大往小排, 如果邊排邊丟, 可能最后排好的部分全在nums1的后面, 仍然需要遍歷一次, 把所有數(shù)挪回左邊. 如果排完再丟, 也是遍歷一次, 感覺沒啥區(qū)別.

所以這兩種方式, 先排再丟和邊排邊丟似乎是沒有區(qū)別的, 大家可以自己思考一下, 有問題歡迎留言評(píng)論.

源碼

Python:

# 直接合并后排序class Solution:    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:        nums1[m:] = nums2        nums1.sort()# 常規(guī)雙指針class Solution:    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:        sorted = []        p1, p2 = 0, 0        while p1 < m or p2 < n: # 同時(shí)到達(dá)尾部才結(jié)束            if p1 == m:                sorted.append(nums2[p2])                p2 += 1            elif p2 == n:                sorted.append(nums1[p1])                p1 += 1            elif nums1[p1] < nums2[p2]:                sorted.append(nums1[p1])                p1 += 1            else:                sorted.append(nums2[p2])                p2 += 1        nums1[:] = sorted   # 對(duì)nums1從頭到尾切片, 相當(dāng)于進(jìn)行了深拷貝# 逆向雙指針class Solution:    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:        p1, p2 = m - 1, n - 1        tail = len(nums1) - 1        while p2 >= 0:            if p1 < 0 or nums1[p1] <= nums2[p2]:                nums1[tail] = nums2[p2]                p2 -= 1                tail -= 1            else:                nums1[tail] = nums1[p1]                p1 -= 1                tail -= 1

java:

// 直接合并后排序class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        for (int i = 0; i != n; ++i) {            nums1[m + i] = nums2[i];        }        Arrays.sort(nums1);    }}// 常規(guī)雙指針class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        int p1 = 0, p2 = 0;        int[] sorted = new int[m + n];        int cur;        while (p1 < m || p2 < n) { // 同時(shí)到達(dá)尾部才結(jié)束            if (p1 == m) {                cur = nums2[p2++];            } else if (p2 == n) {                cur = nums1[p1++];            } else if (nums1[p1] < nums2[p2]) {                cur = nums1[p1++];            } else {                cur = nums2[p2++];            }            sorted[p1 + p2 - 1] = cur;        }        for (int i = 0; i != m + n; ++i) {            nums1[i] = sorted[i];        }    }}// 逆向雙指針class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        int tail = nums1.length - 1;        int p1 = m - 1;        int p2 = n - 1;        while (p2 >= 0) { // 只要p2到達(dá)開頭就結(jié)束            if (p1 < 0 || nums1[p1] <= nums2[p2]) {                nums1[tail--] = nums2[p2--];            } else {                nums1[tail--] = nums1[p1--];            }        }    }}