此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.
想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
文章目錄
- 0.導圖整理
- 1.雙指標的思想
- 2.對于雙指標的優化
- 原始碼
- Python:
- java:
題目鏈接: https://leetcode-cn.com/problems/remove-element/
0.導圖整理
1.雙指標的思想
本題最重要的限制條件就是 原地移除元素, 使用O(1)的額外空間. 如果沒有這個條件限制, 那么本題是非常簡單的, 我們只需要遍歷一遍, 將所有滿足的元素放到另一個陣列就完成操作了. 這樣就會使用到O(n)的空間復雜度.
因為限制條件的存在, 我們必須尋找其他的思想, 只能在原陣列上進行操作, 這樣才能滿足O(1)的空間復雜度. 這樣我們就不光需要找到滿足的元素, 還要同時找到滿足的元素需要存放的位置, 所以我們就需要使用 雙指標 來同時確定這兩個位置.
這就回到了導圖中使用的思想: 右指標right指向當前將要處理的元素, 左指標left指向下一個將要賦值的位置, 這是兩個指標的作用說明. 下面就是兩種實際遍歷中會出現的情況了.
-
如果右指標指向的元素不等于 val, 它一定是輸出陣列的一個元素, 我們就將右指標指向的元素復制到左指標位置, 然后將左右指標同時右移
-
如果右指標指向的元素等于 val, 它不能在輸出陣列里, 此時左指標不動, 右指標右移一位
在 雙指標 進行不斷遍歷的程序中, 我們要從變化中尋找 不變的性質: 區間[0,left) 中的元素都不等于 val，當左右指標遍歷完輸入陣列以后, left 的值就是輸出陣列的長度, 這樣就得到了我們最終需要的結果.
2.對于雙指標的優化
雙指標本就是非常優秀的演算法了, 但是本題還是可以對其再進行優化.
觀察上面的演算法可以發現, 我們都是對滿足條件(會保留下來的資料)進行操作的, 但是最壞的情況下, 如果陣列中沒有需要移除的元素, 那兩個指標就白白地從頭遍歷到尾了. 而且我們根據實際情況來說, 正常情況下 需要移除的元素 必然是遠小于 需要保留的元素的, 那我們直接對 移除元素 進行操作豈不是更有效.
所以依然使用雙指標, 兩個指標初始時分別位于陣列的首尾, 向中間移動遍歷該序列, 只是此時兩指標的含義有所不同: 左指標就是直接指向需要被移除的元素val, 只要滿足條件, 直接用 右指標指向的元素將其替換.
這時候可能會遇到一個問題, 就是如果賦值過來的元素恰好也等于 val怎么辦? 其實這并沒有什么影響, 當右指標向左移動一位之后, 可以繼續把右指標指向的元素的值賦值過來（左指標指向的等于 val 的元素的位置繼續被覆寫）, 直到左指標指向的元素的值不等于 val 為止, 此時左指標向右移動一位.
這樣兩個指標在最壞的情況下合起來只遍歷了陣列一次，與方法一不同的是, 方法二避免了需要保留的元素的重復賦值操作.
這個方法在寫代碼的時候有個注意點: 就是 右指標 的初始值的選取(陣列長度/陣列長度-1), 不同的選取值決定了while的不同回圈條件, 大家可以畫個草圖判斷一下就很明了了.
原始碼
Python:
# 雙指標方法
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
left = 0 # 左指標從0開始,指向下一個將要賦值的位置
# 右指標從0開始,指向當前將要處理的元素
for right in range(0, n):
# 右指標指向的元素不等于val,是輸出陣列的元素
# 將右指標指向的元素復制到左指標位置,然后將左右指標同時右移
if nums[right] != val:
nums[left] = nums[right]
left += 1
# 右指標指向的元素等于val,不在輸出陣列里,左指標不動,右指標右移一位
return left # left的值就是輸出陣列的長度
# 雙指標優化
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left = 0 # 兩個指標初始時分別位于陣列的首尾
right = len(nums)
while left < right:
# 左指標等于val,將右指標元素復制到左指標的位置,右指標左移一位
if nums[left] == val:
nums[left] = nums[right - 1]
right-=1
else : # 左指標不等于val,左指標右移一位,右指標不動
left+=1
return left # left的值就是輸出陣列的長度
java:
// 雙指標方法
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int left = 0; // 左指標從0開始,指向下一個將要賦值的位置
// 右指標從0開始,指向當前將要處理的元素
for (int right = 0; right < n; right++) {
// 右指標指向的元素不等于val,是輸出陣列的元素
// 將右指標指向的元素復制到左指標位置,然后將左右指標同時右移
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
} // 右指標指向的元素等于val,不在輸出陣列里,左指標不動,右指標右移一位
return left; // left的值就是輸出陣列的長度
}
}
// 雙指標優化
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0; // 兩個指標初始時分別位于陣列的首尾
int right = nums.length;
while (left < right) {
// 左指標等于val,將右指標元素復制到左指標的位置,右指標左移一位
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else { // 左指標不等于val,左指標右移一位,右指標不動
left++;
}
}
return left; // left的值就是輸出陣列的長度
}
}
感覺作者寫的不錯的, 別忘了點贊關注加收藏哦(一鍵三連)!你的支持會帶給我極大的動力, 寫出更多優秀文章!
我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 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/houduan/296573.html
標籤：java