??導(dǎo)圖整理大廠面試高頻數(shù)組8: 移除元素的雙指針優(yōu)化, 力扣27??

zhangyucha0 發(fā)布于2021-09-02 15:11 / 2233人閱讀

此專欄文章是對力扣上算法題目各種方法的總結(jié)和歸納, 整理出最重要的思路和知識重點并以思維導(dǎo)圖形式呈現(xiàn), 當(dāng)然也會加上我對導(dǎo)圖的詳解.

目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復(fù)看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經(jīng)知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據(jù)題號先去力扣看看官方題解, 然后再看本文內(nèi)容).

關(guān)于本專欄所有題目的目錄鏈接, 刷算法題目的順序/注意點/技巧, 以及思維導(dǎo)圖源文件問題請點擊此鏈接.

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

文章目錄

0.導(dǎo)圖整理
1.雙指針的思想
2.對于雙指針的優(yōu)化
源碼
Python:
java:

題目鏈接: https://leetcode-cn.com/problems/remove-element/

0.導(dǎo)圖整理

1.雙指針的思想

本題最重要的限制條件就是 原地移除元素, 使用O(1)的額外空間. 如果沒有這個條件限制, 那么本題是非常簡單的, 我們只需要遍歷一遍, 將所有滿足的元素放到另一個數(shù)組就完成操作了. 這樣就會使用到O(n)的空間復(fù)雜度.

因為限制條件的存在, 我們必須尋找其他的思想, 只能在原數(shù)組上進行操作, 這樣才能滿足O(1)的空間復(fù)雜度. 這樣我們就不光需要找到滿足的元素, 還要同時找到滿足的元素需要存放的位置, 所以我們就需要使用雙指針來同時確定這兩個位置.

這就回到了導(dǎo)圖中使用的思想: 右指針right指向當(dāng)前將要處理的元素, 左指針left指向下一個將要賦值的位置, 這是兩個指針的作用說明. 下面就是兩種實際遍歷中會出現(xiàn)的情況了.

如果右指針指向的元素不等于 val, 它一定是輸出數(shù)組的一個元素, 我們就將右指針指向的元素復(fù)制到左指針位置, 然后將左右指針同時右移
如果右指針指向的元素等于 val, 它不能在輸出數(shù)組里, 此時左指針不動, 右指針右移一位

在雙指針進行不斷遍歷的過程中, 我們要從變化中尋找不變的性質(zhì): 區(qū)間[0,left) 中的元素都不等于 val。當(dāng)左右指針遍歷完輸入數(shù)組以后, left 的值就是輸出數(shù)組的長度, 這樣就得到了我們最終需要的結(jié)果.

2.對于雙指針的優(yōu)化

雙指針本就是非常優(yōu)秀的算法了, 但是本題還是可以對其再進行優(yōu)化.

觀察上面的算法可以發(fā)現(xiàn), 我們都是對滿足條件(會保留下來的數(shù)據(jù))進行操作的, 但是最壞的情況下, 如果數(shù)組中沒有需要移除的元素, 那兩個指針就白白地從頭遍歷到尾了. 而且我們根據(jù)實際情況來說, 正常情況下需要移除的元素必然是遠小于需要保留的元素的, 那我們直接對移除元素進行操作豈不是更有效.

所以依然使用雙指針, 兩個指針初始時分別位于數(shù)組的首尾, 向中間移動遍歷該序列, 只是此時兩指針的含義有所不同: 左指針就是直接指向需要被移除的元素val, 只要滿足條件, 直接用右指針指向的元素將其替換.

這時候可能會遇到一個問題, 就是如果賦值過來的元素恰好也等于 val怎么辦? 其實這并沒有什么影響, 當(dāng)右指針向左移動一位之后, 可以繼續(xù)把右指針指向的元素的值賦值過來（左指針指向的等于 val 的元素的位置繼續(xù)被覆蓋）, 直到左指針指向的元素的值不等于 val 為止, 此時左指針向右移動一位.

這樣兩個指針在最壞的情況下合起來只遍歷了數(shù)組一次。與方法一不同的是, 方法二避免了需要保留的元素的重復(fù)賦值操作.

這個方法在寫代碼的時候有個注意點: 就是右指針的初始值的選取(數(shù)組長度/數(shù)組長度-1), 不同的選取值決定了while的不同循環(huán)條件, 大家可以畫個草圖判斷一下就很明了了.

源碼

Python:

# 雙指針方法class Solution:    def removeElement(self, nums: List[int], val: int) -> int:        n = len(nums)        left = 0 # 左指針從0開始,指向下一個將要賦值的位置        # 右指針從0開始,指向當(dāng)前將要處理的元素        for right in range(0, n):            # 右指針指向的元素不等于val,是輸出數(shù)組的元素            # 將右指針指向的元素復(fù)制到左指針位置,然后將左右指針同時右移            if nums[right] != val:                nums[left] = nums[right]                left += 1            # 右指針指向的元素等于val,不在輸出數(shù)組里,左指針不動,右指針右移一位        return left # left的值就是輸出數(shù)組的長度# 雙指針優(yōu)化class Solution:    def removeElement(self, nums: List[int], val: int) -> int:        left = 0 # 兩個指針初始時分別位于數(shù)組的首尾        right = len(nums)        while left < right:            # 左指針等于val,將右指針元素復(fù)制到左指針的位置,右指針左移一位            if nums[left] == val:                nums[left] = nums[right - 1]                right-=1            else : # 左指針不等于val,左指針右移一位,右指針不動                left+=1                          return left # left的值就是輸出數(shù)組的長度

java:

// 雙指針方法class Solution {    public int removeElement(int[] nums, int val) {        int n = nums.length;        int left = 0; // 左指針從0開始,指向下一個將要賦值的位置        // 右指針從0開始,指向當(dāng)前將要處理的元素        for (int right = 0; right < n; right++) {            // 右指針指向的元素不等于val,是輸出數(shù)組的元素            // 將右指針指向的元素復(fù)制到左指針位置,然后將左右指針同時右移            if (nums[right] != val) {                nums[left] = nums[right];                left++;            }        }   // 右指針指向的元素等于val,不在輸出數(shù)組里,左指針不動,右指針右移一位        return left; // left的值就是輸出數(shù)組的長度    }}// 雙指針優(yōu)化class Solution {    public int removeElement(int[] nums, int val) {        int left = 0; // 兩個指針初始時分別位于數(shù)組的首尾        int right = nums.length;        while (left < right) {            // 左指針等于val,將右指針元素復(fù)制到左指針的位置,右指針左移一位            if (nums[left] == val) {                nums[left] = nums[right - 1];                right--;            } else { // 左指針不等于val,左指針右移一位,右指針不動                left++;            }        }        return left; // left的值就是輸出數(shù)組的長度    }}