題目

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
  • Return k.
  • 題目連結

Example 1

1
2
3
4
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

1
2
3
4
5
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).

解釋題目

給你一個 array ( 叫 nums )，跟要去除的數字 ( 叫 val )，題目的條件是不能用新的 array 紀錄，只能更動原本的 array，也就是 in-place 的方式，最後，要回傳 array 中，沒有被移除的數字數量，假設為 k。驗證答案時，只會取 array 中前 k 個值，k 之後的值不會影響驗證。

思路

  1. 在一次的 for 迴圈中，把 array 重新排列
  2. 因為要重新排列 array，所以必須有一個 new_index 去記錄 array 中每個位置，要放甚麼數字
  3. new_index 會從 0 開始
  4. 遍歷 array 的過程中
    • 如果 array[i] 的值 不等於 val ( 要去除的數字 )，array[new_index] 會替換成 array[i]，且 new_index 要往下走一步
    • 如果 array[i] 的值 等於 val ( 要去除的數字 )，new_index 維持原位

圖像拆解

步驟拆解 1

步驟拆解 2

步驟拆解 3

步驟拆解 4

程式碼 (1)

1
2
3
4
5
6
7
8
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        new_idx = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[new_idx] = nums[i]
                new_idx = new_idx + 1
        return new_idx

程式碼 (2)

直覺寫法，用 python remove() 的函式。

1
2
3
4
5
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums:
            nums.remove(val)
        return len(nums)