給你一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。

不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。

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

說明:

為什么返回?cái)?shù)值是整數(shù)，但輸出的答案是數(shù)組呢?

請注意，輸入數(shù)組是以「引用」方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。

你可以想象內(nèi)部操作如下:

// nums 是以“引用”方式傳遞的。也就是說，不對實(shí)參作任何拷貝
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：

輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個(gè)元素均為 2。你不需要考慮數(shù)組中超出新長度后面的元素。例如，函數(shù)返回的新長度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會被視作正確答案。

示例 2：

輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3]
解釋：函數(shù)應(yīng)該返回新的長度 5, 并且 nums 中的前五個(gè)元素為 0, 1, 3, 0, 4。注意這五個(gè)元素可為任意順序。你不需要考慮數(shù)組中超出新長度后面的元素。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-element
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

方法一：雙指針
思路及算法

由于題目要求刪除數(shù)組中等于 \textit{val}val 的元素，因此輸出數(shù)組的長度一定小于等于輸入數(shù)組的長度，我們可以把輸出的數(shù)組直接寫在輸入數(shù)組上。可以使用雙指針：右指針 \textit{right}right 指向當(dāng)前將要處理的元素，左指針 \textit{left}left 指向下一個(gè)將要賦值的位置。

如果右指針指向的元素不等于 \textit{val}val，它一定是輸出數(shù)組的一個(gè)元素，我們就將右指針指向的元素復(fù)制到左指針位置，然后將左右指針同時(shí)右移；

如果右指針指向的元素等于 \textit{val}val，它不能在輸出數(shù)組里，此時(shí)左指針不動，右指針右移一位。

整個(gè)過程保持不變的性質(zhì)是：區(qū)間 [0,\textit{left})[0,left) 中的元素都不等于 \textit{val}val。當(dāng)左右指針遍歷完輸入數(shù)組以后，\textit{left}left 的值就是輸出數(shù)組的長度。

這樣的算法在最壞情況下（輸入數(shù)組中沒有元素等于 \textit{val}val），左右指針各遍歷了數(shù)組一次。

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

方法二：雙指針優(yōu)化
思路

如果要移除的元素恰好在數(shù)組的開頭，例如序列 [1,2,3,4,5][1,2,3,4,5]，當(dāng) \textit{val}val 為 11 時(shí)，我們需要把每一個(gè)元素都左移一位。注意到題目中說：「元素的順序可以改變」。實(shí)際上我們可以直接將最后一個(gè)元素 55 移動到序列開頭，取代元素 11，得到序列 [5,2,3,4][5,2,3,4]，同樣滿足題目要求。這個(gè)優(yōu)化在序列中 \textit{val}val 元素的數(shù)量較少時(shí)非常有效。

實(shí)現(xiàn)方面，我們依然使用雙指針，兩個(gè)指針初始時(shí)分別位于數(shù)組的首尾，向中間移動遍歷該序列。

算法

如果左指針 \textit{left}left 指向的元素等于 \textit{val}val，此時(shí)將右指針 \textit{right}right 指向的元素復(fù)制到左指針 \textit{left}left 的位置，然后右指針 \textit{right}right 左移一位。如果賦值過來的元素恰好也等于 \textit{val}val，可以繼續(xù)把右指針 \textit{right}right 指向的元素的值賦值過來（左指針 \textit{left}left 指向的等于 \textit{val}val 的元素的位置繼續(xù)被覆蓋），直到左指針指向的元素的值不等于 \textit{val}val 為止。

當(dāng)左指針 \textit{left}left 和右指針 \textit{right}right 重合的時(shí)候，左右指針遍歷完數(shù)組中所有的元素。

這樣的方法兩個(gè)指針在最壞的情況下合起來只遍歷了數(shù)組一次。與方法一不同的是，方法二避免了需要保留的元素的重復(fù)賦值操作。

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/remove-element/solution/yi-chu-yuan-su-by-leetcode-solution-svxi/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。