題目網址：https://leetcode.cn/problems/remove-element/

題意：給一整數 array nums 和一整數 val，請 in-place 移除所有數值等於 val 的元素, 並返回移除後 nums 的新長度。

不要使用額外的空間, 設計 $O(1)$ space 的演算法, 並原地修改 nums。

元素的順序可以改變, 不需要考慮 nums 中超出新長度後面的元素。

Solution：

想法：利用 Two Pointers, 先初始化 slow = fast = 0, 用 fast 來遍歷 nums, 而 slow 用來指向新 array 下一個要填入的元素的 index。一旦 nums[fast] != val, 則 nums[slow] = nums[fast], 然後 slow += 1

e.g. nums = [3, 2, 2, 3], val = 3

  • slow = 0, fast = 0, 此時 nums[fast] = 3 = val 跳過
  • slow = 0, fast = 1, 此時 nums[fast] = 2, nums[slow] = 2 ➔ slow = 1
  • slow = 1, fast = 2, 此時 nums[fast] = 2, nums[slow] = 2 ➔ slow = 2
  • slow = 2, fast = 3, 此時 nums[fast] = 3 = val 跳過
  • 做完後 nums = [2, 2, 2, 3], slow = 2 ➔ slow 記錄著新 array 的元素個數, 故新 array 實際上 = [2, 2]
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        const int n = nums.size();
        int slow = 0;

        for (int fast = 0; fast < n; ++fast) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }

        return slow;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(1)$ ➔ 只需常數空間