資訊專欄INFORMATION COLUMN
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷算法題目的順序/注意點/技巧, 以及思維導圖源文件問題請點擊此鏈接.
想進大廠, 刷算法是必不可少的, 歡迎和博主一起打卡刷力扣算法, 博主同步更新了算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
題目鏈接: https://leetcode-cn.com/problems/remove-element/
本題最重要的限制條件就是 原地移除元素, 使用O(1)的額外空間. 如果沒有這個條件限制, 那么本題是非常簡單的, 我們只需要遍歷一遍, 將所有滿足的元素放到另一個數組就完成操作了. 這樣就會使用到O(n)的空間復雜度.
因為限制條件的存在, 我們必須尋找其他的思想, 只能在原數組上進行操作, 這樣才能滿足O(1)的空間復雜度. 這樣我們就不光需要找到滿足的元素, 還要同時找到滿足的元素需要存放的位置, 所以我們就需要使用 雙指針 來同時確定這兩個位置.
這就回到了導圖中使用的思想: 右指針right指向當前將要處理的元素, 左指針left指向下一個將要賦值的位置, 這是兩個指針的作用說明. 下面就是兩種實際遍歷中會出現的情況了.
如果右指針指向的元素不等于 val, 它一定是輸出數組的一個元素, 我們就將右指針指向的元素復制到左指針位置, 然后將左右指針同時右移
如果右指針指向的元素等于 val, 它不能在輸出數組里, 此時左指針不動, 右指針右移一位
在 雙指針 進行不斷遍歷的過程中, 我們要從變化中尋找 不變的性質: 區間[0,left) 中的元素都不等于 val。當左右指針遍歷完輸入數組以后, left 的值就是輸出數組的長度, 這樣就得到了我們最終需要的結果.
雙指針本就是非常優秀的算法了, 但是本題還是可以對其再進行優化.
觀察上面的算法可以發現, 我們都是對滿足條件(會保留下來的數據)進行操作的, 但是最壞的情況下, 如果數組中沒有需要移除的元素, 那兩個指針就白白地從頭遍歷到尾了. 而且我們根據實際情況來說, 正常情況下 需要移除的元素 必然是遠小于 需要保留的元素的, 那我們直接對 移除元素 進行操作豈不是更有效.
所以依然使用雙指針, 兩個指針初始時分別位于數組的首尾, 向中間移動遍歷該序列, 只是此時兩指針的含義有所不同: 左指針就是直接指向需要被移除的元素val, 只要滿足條件, 直接用 右指針指向的元素將其替換.
這時候可能會遇到一個問題, 就是如果賦值過來的元素恰好也等于 val怎么辦? 其實這并沒有什么影響, 當右指針向左移動一位之后, 可以繼續把右指針指向的元素的值賦值過來（左指針指向的等于 val 的元素的位置繼續被覆蓋）, 直到左指針指向的元素的值不等于 val 為止, 此時左指針向右移動一位.
這樣兩個指針在最壞的情況下合起來只遍歷了數組一次。與方法一不同的是, 方法二避免了需要保留的元素的重復賦值操作.
這個方法在寫代碼的時候有個注意點: 就是 右指針 的初始值的選取(數組長度/數組長度-1), 不同的選取值決定了while的不同循環條件, 大家可以畫個草圖判斷一下就很明了了.
# 雙指針方法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的值就是輸出數組的長度// 雙指針方法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++ 歷年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm框架全部筆記
科技相關 小米手機
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.hztianpu.com/yun/118782.html
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...
摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...
閱讀 2555·2021-09-02 15:11
閱讀 1681·2019-08-30 15:43
閱讀 2262·2019-08-29 13:48
閱讀 3002·2019-08-26 13:55
閱讀 2245·2019-08-23 15:09
閱讀 3068·2019-08-23 14:40
閱讀 3703·2019-08-23 14:23
閱讀 2797·2019-08-23 14:20
