https://leetcode.com/problems/remove-duplicates-from-sorted-array/#/description
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
思路1
- 雙指針贬养，i遍歷列表挤土， j在i固定時(shí)掃描列表
- 若list[i] == list[j],刪除list[i]
- 復(fù)雜度太高O(N^2)
#本機(jī)可以，leetcode沒過仰美。。
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 2:
return nums
for i in range(len(nums)):
for j in range(len(nums)):
if i != j and nums[i] == nums[j]:
flag = i
nums.remove(nums[flag])
return len(nums)
思路2
- 注意這里是排序的數(shù)組，意味著重復(fù)的數(shù)字必然連續(xù)出現(xiàn),
- 即蚊夫，若重復(fù)必為list[i] = list[i-1]
思路3
- 設(shè)立newTail壤圃，表示不重復(fù)元素的位置（或者個(gè)數(shù)-1）
- 這里新的list只有前newTail是所需的琅轧，后面無關(guān)緊要 It doesn't matter what you leave beyond the new length.
- i遍歷list伍绳，newTail <= i (當(dāng)無重復(fù)元素時(shí)效床，等號成立)
# Time O(n)
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return len(nums)
newTail = 0
for i in range(1, len(nums)):
if nums[i] != nums[newTail]:
newTail += 1
nums[newTail] = nums[i]
return newTail + 1
