一、題目
給定一個數(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]);
}
二、解題
數(shù)組完成排序后荒椭，我們可以放置兩個指針i 和j谐鼎，其中i 是慢指針，而j 是快指針趣惠。只要nums[i]=nums[j]狸棍，我們就增加j 以跳過重復(fù)項。當我們遇到nums[j]≠nums[i]時信卡，跳過重復(fù)項的運行已經(jīng)結(jié)束隔缀，因此我們必須把它（nums[j]）的值復(fù)制到nums[i]。然后遞增i傍菇，接著我們將再次重復(fù)相同的過程猾瘸，直到j(luò) 到達數(shù)組的末尾為止。
時間復(fù)雜度為O(n),空間復(fù)雜度為O(1).
三、代碼實現(xiàn)
class Solution {
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
if (nums.count == 0) { return 0 }
var i = 0
for j in 0..<nums.count {
if nums[j] != val{
nums[i] = nums[j]
i += 1
}
}
return i
}
}
Demo地址：github
