#26. Remove Duplicates from Sorted Array

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固定时扫描列表
• 若list[i] == list[j],删除list[i]
• 复杂度太高O(N^2)

#本机可以，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

• 注意这里是排序的数组，意味着重复的数字必然连续出现,
• 即，若重复必为list[i] = list[i-1]

思路3

• 设立newTail，表示不重复元素的位置（或者个数-1）
• 这里新的list只有前newTail是所需的，后面无关紧要 It doesn't matter what you leave beyond the new length.
• i遍历list，newTail <= i (当无重复元素时，等号成立)

# 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