此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.
想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
文章目錄
- 0.導圖整理
- 1.雙指標的快慢指標法
- 2.和 移除元素 的不同
- 3.本題的進階版:每個元素最多出現兩次
- 4.本題的通解擴展
- 原始碼
- Python:
- java:
題目鏈接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
0.導圖整理
1.雙指標的快慢指標法
上一篇 移除元素 使用的方法就是雙指標的快慢指標法, 這個方法使用最重要的點就是 明確快慢指標分別代表的含義, 寫代碼之前一定要明確兩者的具體含義, 再來寫代碼就比較容易了.
比如在 移除元素 之中, 我們使用的雙指標: 右指標right指向當前將要處理的元素, 左指標left指向下一個將要賦值的位置. 其實在本題 洗掉有序陣列的重復項 中, 兩個指標的含義和 移除元素 之中的含義是完全相同的: 定義兩個指標 fast 和 slow 分別為快指標和慢指標, 快指標表示遍歷陣列到達的下標位置, 慢指標表示下一個不同元素要填入的下標位置. 在表達上有點差別, 但是本質的思想是完全一致的.
2.和 移除元素 的不同
雖然在雙指標的使用上, 兩者的思想是一致的, 但是具體的使用程序還是有點區別的.
在 移除元素 中, 我們 需要比較的物件 是題目中的給定值, 而且是唯一固定的, 從頭到尾都是沒有任何變化的.
但是在本題中, 我們 需要比較的物件 不再是某個固定的元素了, 而是 快指標指向位置的前一個元素和當前元素的比較, 因為這樣比較, 才能確定兩個相鄰的元素是否為 重復元素, 從而決定是否要保留當前元素, 這是兩題最大的不同點.
還有一個小細節注意下, 因為 移除元素 中被移除的元素可能是任意一個位置的元素, 所以兩個指標的下標都是 從0開始 的. 但是在本題中, 陣列的第一個元素一定是被保留下來的元素, 所以我們直接從 第二個元素 開始遍歷就可以了, 也就是 雙指標的下標都是從1開始的.
3.本題的進階版:每個元素最多出現兩次
進階版和原題的唯一區別就是: 并不是要把所有重復元素都刪去, 而是允許 每個元素最多出現兩次. 改動看似挺簡單, 實則是有一定的難度的, 這也直接讓本題由 簡單 直接提升到 中等 的難度.
如果沒有想通此題的變化, 還是比較難處理的, 很多人也有想到用一個count變數來記錄每個元素出現的次數, 兩次就不處理, 超過兩次就進行洗掉等方法, 但真正實施起來還是有點繞的, 有興趣的朋友可以自己嘗試一下.
我們直接來分析改進后的不同, 也就是進行比較的兩個元素變化了. 在原本的題目中, 只需要比較 快指標指向位置的前一個元素和當前元素 即可滿足要求, 但是此題明顯復雜的多.
首先由于我們并不知道哪些元素會重復多少次, 所以想直接通過快指標指向的元素進行區別是很困難的, 但是這時我們還可以利用慢指標來進行比較. 分析后會發現, 慢指標之前的所有元素都是我們處理好的元素, 也就是 每個元素最多出現兩次, 所以如果 當前待檢查元素 nums[fast] 和 nums[slow?2] 相同的話, 那么它的出現必然就超過了兩次, 因為此時必然有nums[slow?2]=nums[slow?1]=nums[fast], 反正如果不相同, 也就代表 它的出現沒有超過兩次, 這樣我們就找到了 兩個需要比較的物件了, 此題也就沒什么難點了.
4.本題的通解擴展
既然都已經擴展到了 每個元素最多出現兩次了, 那么同樣可以擴展為 每個元素最多出現k次, 這樣就形成了此題的通解問題, 解決了這個問題, 只需把k替換一下, 我們就可以解決任意次數的問題了.
有了兩次的經驗之后, 其實這個擴展也很容易就理解了, 能夠保留的前提是：與當前寫入的位置前面的第 k 個元素進行比較,不相同則保留, 也就是直接比較 nums[slow - k] 和 nums[fast] 兩個元素即可, 在兩次的代碼上稍微修改下就能實作了, 這樣我們就成功的將這一類問題完美的解決了!
原始碼
Python:
# 洗掉有序陣列的重復項
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
fast = slow = 1 # 洗掉重復元素之后也至少剩下一個元素
while fast < n:
if nums[fast] != nums[fast - 1]: # 說明nums[fast] 和之前的元素都不同
nums[slow] = nums[fast] # nums[fast] 的值復制到 nums[slow]
slow += 1
fast += 1
return slow # 從nums[0]到nums[slow?1]的每個元素都不相同
# 洗掉有序陣列中的重復項II 每個元素最多出現兩次
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
if (n <= 2) :
return n
slow, fast = 2, 2 # 陣列的前兩個數必然可以被保留
while (fast < n) :
# 檢查上上個應該被保留的元素nums[slow?2]是否和當前待檢查元素nums[fast]相同
if nums[slow - 2] != nums[fast] :
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow # 從nums[0]到nums[slow?1]的每個元素都不相同
# 通解擴展
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
def solve(k): # 最多保留k位相同數字
slow = 0 # 慢指標從0開始
for fast in nums: # 快指標遍歷整個陣列
# 檢查被保留的元素nums[slow?k]是否和當前待檢查元素fast相同
if slow < k or nums[slow - k] != fast:
nums[slow] = fast
slow += 1
return slow # 從nums[0]到nums[slow?1]的每個元素都不相同
return solve(2)
java:
// 洗掉有序陣列的重復項
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int fast = 1, slow = 1; // 洗掉重復元素之后也至少剩下一個元素
while (fast < n) {
if (nums[fast] != nums[fast - 1]) { // 說明nums[fast] 和之前的元素都不同
nums[slow] = nums[fast]; // nums[fast] 的值復制到 nums[slow]
++slow;
}
++fast;
}
return slow; // 從nums[0]到nums[slow?1]的每個元素都不相同
}
}
// 洗掉有序陣列中的重復項II 每個元素最多出現兩次
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n <= 2) {
return n;
}
int slow = 2, fast = 2; // 陣列的前兩個數必然可以被保留
while (fast < n) {
// 檢查上上個應該被保留的元素nums[slow?2]是否和當前待檢查元素nums[fast]相同
if (nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow; // 從nums[0]到nums[slow?1]的每個元素都不相同
}
}
// 通解擴展
class Solution {
public int removeDuplicates(int[] nums) {
return process(nums, 2);
}
int process(int[] nums, int k) { // 最多保留k位相同數字
int slow = 0; // 慢指標從0開始
for (int fast : nums) { // 快指標遍歷整個陣列
// 檢查被保留的元素nums[slow?k]是否和當前待檢查元素fast相同
if (slow < k || nums[slow - k] != fast) nums[slow++] = fast;
}
return slow; // 從nums[0]到nums[slow?1]的每個元素都不相同
}
}
感覺作者寫的不錯的, 別忘了點贊關注加收藏哦(一鍵三連)!你的支持會帶給我極大的動力, 寫出更多優秀文章!
我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)
最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目
最值得收藏的 計算機網路 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介
最值得收藏的 演算法分析與設計 全部知識點思維導圖整理(北大慕課課程)
最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理
最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)
最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)
最值得收藏的 數字影像處理 全部知識點思維導圖整理(武漢大學慕課課程)
紅黑樹 一張導圖解決紅黑樹全部插入和洗掉問題 包含詳細操作原理 情況對比
各種常見排序演算法的時間/空間復雜度 是否穩定 演算法選取的情況 改進 思維導圖整理
人工智能課件 演算法分析課件 Python課件 數值分析課件 機器學習課件 影像處理課件
考研相關科目 知識點 思維導圖整理
考研經驗–東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)
東南大學 軟體工程 906 資料結構 C++ 歷年真題 思維導圖整理
東南大學 軟體工程 復試3門科目歷年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
高等數學 中值定理 一張思維導圖解決中值定理所有題型
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm框架全部筆記
Spring springmvc Mybatis jsp
科技相關 小米手機
小米 紅米 歷代手機型號大全 發布時間 發布價格
常見手機品牌的各種系列劃分及其特點
歷代CPU和GPU的性能情況和常見后綴的含義 思維導圖整理
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297296.html
標籤：其他