給你一個數(shù)組 nums 和一個值 val枪向，你需要 原地 移除所有數(shù)值等于 val 的元素虚婿，并返回移除后數(shù)組的新長度屋剑。
不要使用額外的數(shù)組空間茵臭，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
元素的順序可以改變胧砰。你不需要考慮數(shù)組中超出新長度后面的元素鳍鸵。
說明:
為什么返回數(shù)值是整數(shù)，但輸出的答案是數(shù)組呢?
請注意朴则，輸入數(shù)組是以「引用」方式傳遞的权纤，這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。
你可以想象內(nèi)部操作如下:
// 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：
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個元素均為 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 中的前五個元素為 0, 1, 3, 0, 4庞萍。注意這五個元素可為任意順序。你不需要考慮數(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 指向當前將要處理的元素，左指針 \textit{left}left 指向下一個將要賦值的位置硅蹦。
如果右指針指向的元素不等于 \textit{val}val荣德，它一定是輸出數(shù)組的一個元素闷煤，我們就將右指針指向的元素復(fù)制到左指針位置，然后將左右指針同時右移命爬；
如果右指針指向的元素等于 \textit{val}val曹傀，它不能在輸出數(shù)組里，此時左指針不動饲宛，右指針右移一位。
整個過程保持不變的性質(zhì)是：區(qū)間 [0,\textit{left})[0,left) 中的元素都不等于 \textit{val}val嗜价。當左右指針遍歷完輸入數(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]瑟由，當 \textit{val}val 為 11 時絮重，我們需要把每一個元素都左移一位。注意到題目中說：「元素的順序可以改變」歹苦。實際上我們可以直接將最后一個元素 55 移動到序列開頭青伤，取代元素 11，得到序列 [5,2,3,4][5,2,3,4]殴瘦，同樣滿足題目要求狠角。這個優(yōu)化在序列中 \textit{val}val 元素的數(shù)量較少時非常有效。
實現(xiàn)方面蚪腋，我們依然使用雙指針丰歌，兩個指針初始時分別位于數(shù)組的首尾，向中間移動遍歷該序列屉凯。
算法
如果左指針 \textit{left}left 指向的元素等于 \textit{val}val立帖，此時將右指針 \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 為止哩簿。
當左指針 \textit{left}left 和右指針 \textit{right}right 重合的時候宵蕉，左右指針遍歷完數(shù)組中所有的元素。
這樣的方法兩個指針在最壞的情況下合起來只遍歷了數(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)載請注明出處薄榛。
