leetcode

刪除排序數組中的重復項

給你一個有序數組 nums ，請你 原地 刪除重復出現的元素，使每個元素 只出現一次 ，返回刪除後數組的新長度。

不要使用額外的數組空間，你必須在 原地 修改輸入數組 並在使用 O(1) 額外空間的條件下完成。

說明:

 為什麼返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數裡修改輸入數組對於調用者是可見的。
你可以想象內部操作如下:
// nums 是以“引用”方式傳遞的。也就是說，不對實參做任何拷貝 int len = removeDuplicates(nums);
// 在函數裡修改輸入數組對於調用者是可見的。 // 根據你的函數返回的長度, 它會打印出數組中 該長度范圍內 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }

示例 1：

輸入：nums = [1,1,2]
輸出：2, nums = [1,2]
解釋：函數應該返回新的長度 2 ，並且原數組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數組中超出新長度後面的元素。

示例 2：

輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數應該返回新的長度 5 ， 並且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 。不需要考慮數組中超出新長度後面的元素。

提示：

0 <= nums.length <= 3 * 104shi de si ci fang
-104 <= nums[i] <= 104
nums 已按升序排列

作者：力扣 (LeetCode)
鏈接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

Solution1

for循環刪除元素，其他元素的下標都會被改變。

• solution1 分兩層循環，定義一個變量 存儲上一個元素的值。
• 列表為空，則不進入內層循環。
• 內層循環一旦找到符合條件的元素，則刪除。
• 刪除則，跳出內層循環，繼續從頭開始循環新的列表。
• 如果循環到列表的最後一個元素，則flag為False，跳出所有循環。
• 程序結束。

class Solution:
def removeDuplicates(self, nums) -> int:
flag = True #循環標識
while flag:
if nums == []:
break
before = "" #存儲前一個元素
for i in nums:
if nums.index(i) == len(nums)-1:
flag = False #如果循環到最後一個元素，flag為False結束循環
if i == before:# 如果i等於上一個元素，則刪除i，跳出本次循環，繼續 從0循環列表
nums.remove(i)
break
before = i #將 i 賦值給before
return len(nums)
if __name__ == '__main__':
nums = [[1,1,2],
[0, 0, 1, 1, 1, 2, 2, 3, 3, 4],
[],
[1]
]
exp = [(2,[1,2]),
(5,[0,1,2,3,4]),
(0,[]),
(1,[1])
]
s = Solution()
for num in nums:
print("------start------")
print("num = %s " % str(num))
res = s.removeDuplicates(num)
print("exp = %s "%str(exp[nums.index(num)]))
print("res = %s "%str((res,num)))
print("result = %s "%str((res,num)==exp[nums.index(num)]))
print("-------end-------")

Solution2

• 定義count存儲刪除元素次數
• 列表不為空則進入循環
• 循環列表index，如果上個元素值等於當前值且當前元素index非0（確保當前不是第一個元素），則刪除當前元素，count加1

 def removeDuplicates2(self, nums) -> int:
count = 0 #被刪除的次數
if nums:
for i in range(len(nums)):
if i>0 and nums[i-count] == nums[i-count-1]:
del nums[i-count]
count += 1
return len(nums)

Solution3（最佳）

列表逆序刪除，未被刪除的元素下標不會被改變。避免了循環刪除出現的下標改變的問題。

 def removeDuplicates3(self, nums) -> int:
for i in range(len(nums) - 1, 0, -1):#逆序刪除
if nums[i] == nums[i - 1]:
del nums[i]
return len(nums)