一、問題

給定一個數(shù)組 nums 和一個值 val，原地移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。不能使用額外的數(shù)組空間，必須僅使用 O(1) 額外空間并原地修改輸入數(shù)組。元素的順序可以改變，不需要考慮數(shù)組中超出新長度后面的元素。

示例 1：給定 nums=[3,2,2,3]，val=3。函數(shù)返回新的長度 2，并且 nums 中的前兩個元素均為 2。

示例 2：給定 nums=[0,1,2,2,3,0,4,2]，val=2。函數(shù)返回新的長度 5，并且 nums 中的前五個元素為 0, 1, 3, 0, 4。

說明：

為什么返回數(shù)值是整數(shù)，但輸出的答案是數(shù)組呢？請注意，輸入數(shù)組是以「引用」方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。

//nums 是以“引用”方式傳遞的。也就是說，不對實參作任何拷貝
int len = removeElement(nums, val);

//在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。
//根據(jù)你的函數(shù)返回的長度，它會打印出數(shù)組中該長度范圍內(nèi)的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

二、解答

1??雙指針
問題要求就地刪除給定值的所有元素，就必須用 O(1) 的額外空間來處理它。如何解決？可以保留兩個指針 i 和 j，其中 i 是慢指針，j 是快指針。當 nums[j] 與給定的值相等時，遞增 j 以跳過該元素。只要 nums[j] 不等于 val，就復制 nums[j] 到 nums[i] 并同時遞增兩個索引。重復這一過程，直到 j 到達數(shù)組的末尾，該數(shù)組的新長度為 i。該解法與刪除排序數(shù)組中的重復項的解法十分相似。

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

①時間復雜度：O(n)，假設數(shù)組總共有 n 個元素，i 和 j 至少遍歷 2n 步。
②空間復雜度：O(1)。

2??雙指針 —— 當要刪除的元素很少時
例如，num=[1，2，3，5，4]，val=4。之前的算法會對前四個元素做不必要的復制操作。另一個例子是 num=[4，1，2，3，5]，val=4。似乎沒有必要將 [1，2，3，5] 這幾個元素左移一步，因為問題描述中提到元素的順序可以更改。

當遇到 nums[i]=val 時，可以將當前元素與最后一個元素進行交換，并釋放最后一個元素。這實際上使數(shù)組的大小減小了 1。被交換的最后一個元素可能是想要移除的值。但是不要擔心，在下一次迭代中，仍然會檢查這個元素。

public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

①時間復雜度：O(n)，i 和 n 最多遍歷 n 步。在這個方法中，賦值操作的次數(shù)等于要刪除的元素的數(shù)量。因此，如果要移除的元素很少，效率會更高。
②空間復雜度：O(1)。