一魚三吃 用雙指針的觀念來解 Remove Element 移除元素 Leetcode #27

這題的題目在這裡

雖然表面是一道移除元素的題目，但實際上考的還是搬移。

題目要求的是把val目標值移除，等價於 把非目標值的搬到前面，並且回傳這些剩下來的元素個數(也就是 陣列裡面，非目標值的元素總數​)。

請看下方範例，會更好理解。

測試範例:

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

約束條件:

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

演算法:

其實這題也是換湯不換藥，基本上就是Move Zeroes的孿生題。

前面那題要求的是 把等於零的數字搬到後面。

這題要求的是 把等於val的數字搬到後面，並且回傳剩下那些不等於val的數字的總數。

依樣畫葫蘆，我們統計val的出現次數，再作交換(把等於val的搬到後面，不等於val的數字搬到前面)。

再依據一個基本性質:

等於val的數字總數 + 不等於val的數字總數 = 原本陣列長度

做一個簡單的移向項，我們可以得到:

不等於val的數字總數

= 原本陣列長度 - 等於val的數字總數

= len(nums) - targetCount

= 最終回傳答案

程式碼:

class Solution:
　def removeElement(self, nums: List[int], val: int) -> int:
　　
　　targetCount = 0

　　for i in range( len(nums) ):

　　　if nums[i] == val:
　　　　targetCount += 1
　　　
　　　elif targetCount > 0:
　　　　nums[ i - targetCount ], nums[i] = nums[i], nums[ i - targetCount ]

　　return len(nums) - targetCount

時間複雜度:

O( n ) 一個單層的 for loop 迭代，掃描過每個數字一次。

空間複雜度:

O(1) 只用到固定的臨時變數 和 計數器，所占用的記憶體空間為常數級別O(1)

學完這題之後，記得回去複習原本的那一題 Sort Array by Parity，
Move Zeroes 這兩題。
背後的核心觀念，都是數字先分類成兩群
(奇數 偶數、等於零 不等於零、等於val 不等於val)，再做移動的操作。

Reference:

[1] Python/JS/Go/C++ O(n) by two-pointers - Remove Element - LeetCode