Python實現(xiàn)：
```
class Solution:
? ? def removeElement(self, nums, val):
? ? ? ? """
? ? ? ? :type nums: List[int]
? ? ? ? :type val: int
? ? ? ? :rtype: int
? ? ? ? """
? ? ? ? i = nums.count(val)
? ? ? ? j = len(nums)
? ? ? ? while val in nums:
? ? ? ? ? ? nums.remove(val)
? ? ? ? return j-i
```
給定一個數(shù)組?nums?和一個值?val，你需要原地移除所有數(shù)值等于val?的元素，返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。
示例 1:
給定nums=[3,2,2,3],val=3,函數(shù)應(yīng)該返回新的長度2, 并且nums 中的前兩個元素均為2。你不需要考慮數(shù)組中超出新長度后面的元素。
示例?2:
給定nums=[0,1,2,2,3,0,4,2],val=2,函數(shù)應(yīng)該返回新的長度5, 并且nums 中的前五個元素為0,1,3,0,4。注意這五個元素可為任意順序。你不需要考慮數(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]);}
概要
這是一個相當(dāng)簡單的問題，但人們可能會對“就地”一詞感到困惑，并認(rèn)為在不復(fù)制數(shù)組的情況下從數(shù)組中刪除元素是不可能的。
提示
嘗試雙指針法。
你是否使用“元素順序可以更改”這一屬性？
當(dāng)要刪除的元素很少時會發(fā)生什么？
解決方案
方法一：雙指針
思路
既然問題要求我們就地刪除給定值的所有元素，我們就必須用?O(1)O(1)?的額外空間來處理它。如何解決？我們可以保留兩個指針?ii?和?jj，其中?ii?是慢指針，jj?是快指針。
算法
當(dāng)?nums[j]nums[j]?與給定的值相等時，遞增?jj?以跳過該元素。只要?nums[j] \neq valnums[j]?=val，我們就復(fù)制?nums[j]nums[j]?到?nums[i]nums[i]?并同時遞增兩個索引。重復(fù)這一過程，直到?jj?到達數(shù)組的末尾，該數(shù)組的新長度為?ii。
該解法與?刪除排序數(shù)組中的重復(fù)項?的解法十分相似。
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;
}
復(fù)雜度分析
時間復(fù)雜度：O(n)O(n)， 假設(shè)數(shù)組總共有?nn?個元素，ii?和?jj?至少遍歷?2n2n?步。
空間復(fù)雜度：O(1)O(1)。?
方法二：雙指針 —— 當(dāng)要刪除的元素很少時
思路
現(xiàn)在考慮數(shù)組包含很少的要刪除的元素的情況。例如，num=[1，2，3，5，4]，Val=4num=[1，2，3，5，4]，Val=4。之前的算法會對前四個元素做不必要的復(fù)制操作。另一個例子是?num=[4，1，2，3，5]，Val=4num=[4，1，2，3，5]，Val=4。似乎沒有必要將?[1，2，3，5][1，2，3，5]?這幾個元素左移一步，因為問題描述中提到元素的順序可以更改。
算法
當(dāng)我們遇到?nums[i] = valnums[i]=val?時，我們可以將當(dāng)前元素與最后一個元素進行交換，并釋放最后一個元素。這實際上使數(shù)組的大小減少了 1。
請注意，被交換的最后一個元素可能是您想要移除的值。但是不要擔(dān)心，在下一次迭代中，我們?nèi)匀粫z查這個元素。
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;
}
復(fù)雜度分析
時間復(fù)雜度：O(n)O(n)，ii?和?nn?最多遍歷?nn?步。在這個方法中，賦值操作的次數(shù)等于要刪除的元素的數(shù)量。因此，如果要移除的元素很少，效率會更高。
空間復(fù)雜度：O(1)O(1)。
