??思維導(dǎo)圖整理大廠面試高頻數(shù)組9: 刪除重復(fù)元素的通解問(wèn)題, 力扣26/80??

MasonEast 發(fā)布于2021-09-04 16:40 / 2508人閱讀

此專(zhuān)欄文章是對(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)于本專(zhuān)欄所有題目的目錄鏈接, 刷算法題目的順序/注意點(diǎn)/技巧, 以及思維導(dǎo)圖源文件問(wèn)題請(qǐng)點(diǎn)擊此鏈接.

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

文章目錄

0.導(dǎo)圖整理
1.雙指針的快慢指針?lè)?/a>
2.和移除元素的不同
3.本題的進(jìn)階版:每個(gè)元素最多出現(xiàn)兩次
4.本題的通解擴(kuò)展
源碼
Python:
java:

題目鏈接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/

0.導(dǎo)圖整理

1.雙指針的快慢指針?lè)?/h2>
上一篇移除元素使用的方法就是雙指針的快慢指針?lè)? 這個(gè)方法使用最重要的點(diǎn)就是明確快慢指針?lè)謩e代表的含義, 寫(xiě)代碼之前一定要明確兩者的具體含義, 再來(lái)寫(xiě)代碼就比較容易了.

比如在移除元素之中, 我們使用的雙指針: 右指針right指向當(dāng)前將要處理的元素, 左指針left指向下一個(gè)將要賦值的位置. 其實(shí)在本題刪除有序數(shù)組的重復(fù)項(xiàng) 中, 兩個(gè)指針的含義和移除元素之中的含義是完全相同的: 定義兩個(gè)指針 fast 和 slow 分別為快指針和慢指針, 快指針表示遍歷數(shù)組到達(dá)的下標(biāo)位置, 慢指針表示下一個(gè)不同元素要填入的下標(biāo)位置. 在表達(dá)上有點(diǎn)差別, 但是本質(zhì)的思想是完全一致的.

2.和移除元素的不同

雖然在雙指針的使用上, 兩者的思想是一致的, 但是具體的使用過(guò)程還是有點(diǎn)區(qū)別的.

在移除元素中, 我們需要比較的對(duì)象是題目中的給定值, 而且是唯一固定的, 從頭到尾都是沒(méi)有任何變化的.

但是在本題中, 我們需要比較的對(duì)象不再是某個(gè)固定的元素了, 而是快指針指向位置的前一個(gè)元素和當(dāng)前元素的比較, 因?yàn)檫@樣比較, 才能確定兩個(gè)相鄰的元素是否為重復(fù)元素, 從而決定是否要保留當(dāng)前元素, 這是兩題最大的不同點(diǎn).

還有一個(gè)小細(xì)節(jié)注意下, 因?yàn)?移除元素中被移除的元素可能是任意一個(gè)位置的元素, 所以兩個(gè)指針的下標(biāo)都是從0開(kāi)始的. 但是在本題中, 數(shù)組的第一個(gè)元素一定是被保留下來(lái)的元素, 所以我們直接從第二個(gè)元素開(kāi)始遍歷就可以了, 也就是雙指針的下標(biāo)都是從1開(kāi)始的.

3.本題的進(jìn)階版:每個(gè)元素最多出現(xiàn)兩次

進(jìn)階版和原題的唯一區(qū)別就是: 并不是要把所有重復(fù)元素都刪去, 而是允許每個(gè)元素最多出現(xiàn)兩次. 改動(dòng)看似挺簡(jiǎn)單, 實(shí)則是有一定的難度的, 這也直接讓本題由簡(jiǎn)單直接提升到中等的難度.

如果沒(méi)有想通此題的變化, 還是比較難處理的, 很多人也有想到用一個(gè)count變量來(lái)記錄每個(gè)元素出現(xiàn)的次數(shù), 兩次就不處理, 超過(guò)兩次就進(jìn)行刪除等方法, 但真正實(shí)施起來(lái)還是有點(diǎn)繞的, 有興趣的朋友可以自己嘗試一下.

我們直接來(lái)分析改進(jìn)后的不同, 也就是進(jìn)行比較的兩個(gè)元素變化了. 在原本的題目中, 只需要比較快指針指向位置的前一個(gè)元素和當(dāng)前元素即可滿足要求, 但是此題明顯復(fù)雜的多.

首先由于我們并不知道哪些元素會(huì)重復(fù)多少次, 所以想直接通過(guò)快指針指向的元素進(jìn)行區(qū)別是很困難的, 但是這時(shí)我們還可以利用慢指針來(lái)進(jìn)行比較. 分析后會(huì)發(fā)現(xiàn), 慢指針之前的所有元素都是我們處理好的元素, 也就是每個(gè)元素最多出現(xiàn)兩次, 所以如果當(dāng)前待檢查元素 nums[fast] 和 nums[slow?2] 相同的話, 那么它的出現(xiàn)必然就超過(guò)了兩次, 因?yàn)榇藭r(shí)必然有nums[slow?2]=nums[slow?1]=nums[fast], 反正如果不相同, 也就代表它的出現(xiàn)沒(méi)有超過(guò)兩次, 這樣我們就找到了兩個(gè)需要比較的對(duì)象了, 此題也就沒(méi)什么難點(diǎn)了.

4.本題的通解擴(kuò)展

既然都已經(jīng)擴(kuò)展到了每個(gè)元素最多出現(xiàn)兩次了, 那么同樣可以擴(kuò)展為每個(gè)元素最多出現(xiàn)k次, 這樣就形成了此題的通解問(wèn)題, 解決了這個(gè)問(wèn)題, 只需把k替換一下, 我們就可以解決任意次數(shù)的問(wèn)題了.

有了兩次的經(jīng)驗(yàn)之后, 其實(shí)這個(gè)擴(kuò)展也很容易就理解了, 能夠保留的前提是：與當(dāng)前寫(xiě)入的位置前面的第 k 個(gè)元素進(jìn)行比較,不相同則保留, 也就是直接比較 nums[slow - k] 和 nums[fast] 兩個(gè)元素即可, 在兩次的代碼上稍微修改下就能實(shí)現(xiàn)了, 這樣我們就成功的將這一類(lèi)問(wèn)題完美的解決了!

源碼

Python:

# 刪除有序數(shù)組的重復(fù)項(xiàng)class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        if not nums:            return 0                n = len(nums)        fast = slow = 1 # 刪除重復(fù)元素之后也至少剩下一個(gè)元素        while fast < n:            if nums[fast] != nums[fast - 1]: # 說(shuō)明nums[fast] 和之前的元素都不同                nums[slow] = nums[fast]      # nums[fast] 的值復(fù)制到 nums[slow]                slow += 1            fast += 1                return slow # 從nums[0]到nums[slow?1]的每個(gè)元素都不相同        # 刪除有序數(shù)組中的重復(fù)項(xiàng)II 每個(gè)元素最多出現(xiàn)兩次class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        n = len(nums)        if (n <= 2) :            return n                slow, fast = 2, 2 # 數(shù)組的前兩個(gè)數(shù)必然可以被保留        while (fast < n) :            # 檢查上上個(gè)應(yīng)該被保留的元素nums[slow?2]是否和當(dāng)前待檢查元素nums[fast]相同            if nums[slow - 2] != nums[fast] :                nums[slow] = nums[fast]                slow += 1            fast += 1                return slow # 從nums[0]到nums[slow?1]的每個(gè)元素都不相同        # 通解擴(kuò)展class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        def solve(k): # 最多保留k位相同數(shù)字            slow = 0 # 慢指針從0開(kāi)始            for fast in nums: # 快指針遍歷整個(gè)數(shù)組                # 檢查被保留的元素nums[slow?k]是否和當(dāng)前待檢查元素fast相同                if slow < k or nums[slow - k] != fast:                    nums[slow] = fast                    slow += 1            return slow # 從nums[0]到nums[slow?1]的每個(gè)元素都不相同        return solve(2)

java:

// 刪除有序數(shù)組的重復(fù)項(xiàng)class Solution {    public int removeDuplicates(int[] nums) {        int n = nums.length;        if (n == 0) {            return 0;        }        int fast = 1, slow = 1; // 刪除重復(fù)元素之后也至少剩下一個(gè)元素        while (fast < n) {            if (nums[fast] != nums[fast - 1]) { // 說(shuō)明nums[fast] 和之前的元素都不同                nums[slow] = nums[fast];        // nums[fast] 的值復(fù)制到 nums[slow]                ++slow;            }            ++fast;        }        return slow; // 從nums[0]到nums[slow?1]的每個(gè)元素都不相同    }}// 刪除有序數(shù)組中的重復(fù)項(xiàng)II 每個(gè)元素最多出現(xiàn)兩次class Solution {    public int removeDuplicates(int[] nums) {        int n = nums.length;        if (n <= 2) {            return n;        }        int slow = 2, fast = 2; // 數(shù)組的前兩個(gè)數(shù)必然可以被保留        while (fast < n) {            // 檢查上上個(gè)應(yīng)該被保留的元素nums[slow?2]是否和當(dāng)前待檢查元素nums[fast]相同            if (nums[slow - 2] != nums[fast]) {                nums[slow] = nums[fast];                ++slow;            }            ++fast;        }        return slow; // 從nums[0]到nums[slow?1]的每個(gè)元素都不相同    }}// 通解擴(kuò)展class Solution {    public int removeDuplicates(int[] nums) {           return process(nums, 2);    }    int process(int[] nums, int k) { // 最多保留k位相同數(shù)字        int slow = 0; // 慢指針從0開(kāi)始        for (int fast : nums) { // 快指針遍歷整個(gè)數(shù)組            // 檢查被保留的元素nums[slow?k]是否和當(dāng)前待檢查元素fast相同            if (slow < k || nums[slow - k] != fast) nums[slow++] = fast;        }        return slow; // 從nums[0]到nums[slow?1]的每個(gè)元素都不相同    }}