- 給你一個有序數(shù)組 nums 豁生，請你 原地 刪除重復(fù)出現(xiàn)的元素，使每個元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度傍睹。
- 不要使用額外的數(shù)組空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成犹菱。
說明:
- 為什么返回數(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]);
}
示例 1：
輸入：nums = [1,1,2]
輸出：2, nums = [1,2]
解釋：函數(shù)應(yīng)該返回新的長度 2 杜耙，并且原數(shù)組 nums 的前兩個元素被修改為 1, 2 搜骡。不需要考慮數(shù)組中超出新長度后面的元素。
示例 2：
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數(shù)應(yīng)該返回新的長度 5 佑女， 并且原數(shù)組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 记靡。不需要考慮數(shù)組中超出新長度后面的元素。
提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列
答題
1.簡單思路：
遍歷nums团驱，將將相鄰的前后兩位進行比較摸吠，相等刪除重復(fù)值，不相等繼續(xù)遍歷嚎花，直到遍歷完成寸痢。
出現(xiàn)問題：
遍歷法思路沒問題，但是題目要求在原地刪除修改紊选，這也意味著遍歷時候如果進行刪除會報錯啼止，原因是在刪除list中的元素后道逗，list的實際長度變小了，但是循環(huán)次數(shù)沒有減少献烦，依然按照原來list的長度進行遍歷憔辫，所以會造成索引溢出。
解決思路：
反向遍歷刪除法仿荆，因為從數(shù)組尾部刪除元素贰您，不會影響到其他元素。
代碼實例
from typing import List
nums = [0,0,1,1,1,2,2,3,3,4]
# 倒序法
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) <= 0:
return 0
for i in range(len(nums)-1, 0, -1):
if nums[i] == nums[i-1]:
nums.pop(i)
return len(nums)
2.快慢指針法
解題思路
由題意可知拢操，列表是有序的锦亦，而且需要返回移除后新元素的長度。那么我們得到如下幾個關(guān)鍵信息：
重復(fù)元素必然相鄰令境。
只需要返回有序且不重復(fù)列表長度杠园。
你不需要考慮數(shù)組中超出新長度后面的元素。
簡單思路：
結(jié)合原地算法的要求舔庶，我們可以將重復(fù)的元素移動到數(shù)組右側(cè)抛蚁，然后返回不重復(fù)且有序的元素即數(shù)組左側(cè)長度。切片的時間復(fù)雜度為O(n)惕橙，所有我們可以通過快慢指針來進行對比賦值瞧甩，通過指針移動步數(shù)就可以知道不重復(fù)且有序數(shù)組的長度。
參考圖片：
image.png
4.2 代碼實例
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
slow = 0 # 慢指針
for i in range(1, len(nums)):
if nums[i] != nums[slow]:
slow += 1
nums[slow] = nums[i]
print(slow+1)
return slow+1
