給定一個排序數(shù)組瘟裸，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度域慷。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
示例 1:
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2犹褒。
你不需要考慮數(shù)組中超出新長度后面的元素抵窒。</pre>
示例 2:
給定數(shù)組nums = [0,0,1,1,1,2,2,3,3,4],
函數(shù)應(yīng)該返回新的長度 5, 并且原數(shù)組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。
你不需要考慮數(shù)組中超出新長度后面的元素化漆。
說明:
為什么返回數(shù)值是整數(shù)估脆，但輸出的答案是數(shù)組呢?
請注意，輸入數(shù)組是以“引用”方式傳遞的座云，這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的疙赠。
你可以想象內(nèi)部操作如下:
**nums** 是以“引用”方式傳遞的。也就是說朦拖，不對實參做任何拷貝
int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的圃阳。
// 根據(jù)你的函數(shù)返回的長度, 它會打印出數(shù)組中**該長度范圍內(nèi)**的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
逆序遍歷法
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
j = 0
for j in range(len(nums)-1, 0, -1):
if nums[j] == nums[j-1]:
nums.pop(j-1)
return len(nums)
雙指針法
數(shù)組完成排序后璧帝，我們可以放置兩個指針 i 和 j捍岳，其中 i 是慢指針，而 j 是快指針睬隶。只要 nums[i]=nums[j]锣夹，我們就增加 j 以跳過重復(fù)項。
當我們遇到 nums[j] != nums[i] 時苏潜，跳過重復(fù)項的運行已經(jīng)結(jié)束银萍，因此我們必須把它nums[j]的值復(fù)制到 nums[i+1]。然后遞增 i恤左，接著我們將再次重復(fù)相同的過程贴唇，直到 j 到達數(shù)組的末尾為止。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1
