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

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

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

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

文章目錄

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

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

0.導(dǎo)圖整理

1.雙指針的思想

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

因?yàn)橄拗茥l件的存在, 我們必須尋找其他的思想, 只能在原數(shù)組上進(jìn)行操作, 這樣才能滿足O(1)的空間復(fù)雜度. 這樣我們就不光需要找到滿足的元素, 還要同時(shí)找到滿足的元素需要存放的位置, 所以我們就需要使用雙指針來(lái)同時(shí)確定這兩個(gè)位置.

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

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

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

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

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

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

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

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

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

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

源碼

Python:

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

java:

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