題目描述

原題鏈接：LeetCode 27. 移除元素

給定一個數組 nums 和一個值 val，你需要原地移除所有數值等于 val 的元素，返回移除后數組的新長度。

不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。

元素的順序可以改變。你不需要考慮數組中超出新長度后面的元素。

示例 1:

給定 nums = [3,2,2,3], val = 3,函數應該返回新的長度 2, 并且 nums 的前兩個元素均為 2。你不需要考慮數組中超出新長度后面的元素。

示例 2:

給定 nums = [0,1,2,2,3,0,4,2], val = 2,函數應該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4。注意這五個元素可為任意順序。你不需要考慮數組中超出新長度后面的元素。

說明:

為什么返回數值是整數，但輸出的答案是數組呢?

請注意，輸入數組是以“引用”方式傳遞的，這意味著在函數里修改輸入數組對于調用者是可見的。

你可以想象內部操作如下:

// nums 是以“引用”方式傳遞的。也就是說，不對實參作任何拷貝 int len = removeElement(nums, val);// 在函數里修改輸入數組對于調用者是可見的。 // 根據你的函數返回的長度, 它會打印出數組中該長度范圍內的所有元素。 for (int i = 0; i < len; i++) {print(nums[i]); }

題意解讀

劃一下題目的重點：

• 原地移除
• 不要使用額外的數組空間
• 不需要考慮數組中超出新長度后面的元素

題目要求我們原地刪除所有等于 val 的元素，不能使用額外空間，且不用考慮刪除后超出新數組長度后面的元素。

也就是說，如果原數組 nums 長度為 x，要刪除的 val 元素個數為 y，那么我們只要把這 n 個要刪除的元素所在位置用其他有效元素覆蓋掉，然后返回最終的數組長度 x - y。

題目并非讓我們真的刪除數組的元素，而是要改寫相關元素的值。

思路闡述

那么要如何進行元素的改寫呢？

既然要讓 val 元素都堆在數組尾部，那么我們就派出一個開拓者探路，只要遇到非 val 元素，就把它覆蓋到前面來。

因此，我們可以定義兩個指針：

• 快指針 j：用于尋找非 val 元素
• 慢指針 i：當 j 找到非 val 元素時，就被非 val 元素覆蓋

圖解思路

以題中的 nums = [3,2,2,3], val = 3 為例。

開始時 i 和 j 都指向下標 0 位置：

此時 j 指向的元素為 val，所以把 j 右移動 1 位：

此時，開拓者 j 找到了一個非 val 元素，那么就賦值給 i 吧：

賦值以后，我們得到了一個新的序列 [2, 2, 2, 3]，我們可以得知：

• i 指向的元素一定不是 val，因為它是從 j 指向的元素賦值得來的，j 指向非 val 元素才會進行賦值
• j 指向的元素一定不是非 val？？？

這樣一來，i 和 j 都完成了本輪使命，繼續前進！

因此每次交換以后，我們都同步增長雙指針，令 i = i + 1，j = j + 1：

此時 j 又指向了一個非 val 元素，繼續賦值：

因為本次 i 與 j 指向元素相同，所以賦值后序列沒有改變。賦值操作后，我們繼續同步增長雙指針：

此時 j 指向了一個 val 元素，無法進行賦值操作，繼續增長 j，令 j = j + 1：

此時我們發現 j 超出數組范圍了，循環結束。[2, 2, 2, 3] 即為我們最終所求結果，而紅色部分即為新數組長度，長度為 len(nums) - (j - i)。

總結一下

設置雙指針 i 和 j，其中，j 用于尋找非 val 元素，來覆蓋 i 所指向的元素。

• 初始時：設 i = 0, j = 0
• 遍歷數組：
  • 若 `nums[j] != val`：
    • 把 `j` 的值賦給 `i`：`nums[i] = nums[j]`
    • 同步增長雙指針：`i = i + 1, j = j + 1`

• • 若 `nums[j] == val`：
    • `j` 變為快指針：`j = j + 1`，尋找下一個非 `val` 元素

具體實現

Python

class Solution:def removeElement(self, nums, val):""":type nums: List[int]:type val: int:rtype: int"""length = len(nums)i = 0j = 0while j < length:if nums[j] != val:nums[i] = nums[j]i = i + 1j = j + 1else:j = j + 1res = length - (j - i)return res

Golang

func removeElement(nums []int, val int) int {length := len(nums)if length == 0 {return 0}i := 0j := 0for j < length {if nums[j] == val {// 去找一個不是 val 的值j++} else {// 賦值nums[i] = nums[j]i++ j++}}return length - (j - i) }

復雜度

• 時間復雜度：O(n)
• 空間復雜度：O(1)，沒有使用到額外空間。

---

• 我的題解項目: https://github.com/JalanJiang/leetcode-notebook
• 如果你對做題和分享題解感興趣，歡迎加入 LeetCode 刷題小分隊：https://github.com/leetcode-notebook/leetcode-notebook.github.io/blob/master/README.md
• 如果你覺得文章寫得不錯，歡迎關注公眾號「編程拯救世界」，公眾號專注于編程基礎與服務端研發，定期分享算法與數據結構干貨~

總結

以上是生活随笔為你收集整理的lrange是取出所有值并移除么_图解双指针 | LeetCode 27. 移除元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。