026.removeduplicatesfromsortedarray.md

26. Remove Duplicates from Sorted Array

Question：

Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.

Example:

Given 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 returned length.

Analysis:

在一个排序好的数组里面删除重复的元素。首先我们需要知道，对于一个排好序的数组来说，A[N + 1] >= A[N]，我们仍然使用两个游标i和j来处理，假设现在i = j + 1，如果A[i] == A[j]，那么我们递增i，直到A[i] != A[j]，这时候我们再设置A[j + 1] = A[i]，同时递增i和j，重复上述过程直到遍历结束。 代码如下：

Solution:

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i=0
        j=0
        l=len(nums)
        if nums == []:
            return (0)
        while ( i<l and j<l ):
            if nums[i]==nums[j]:
                i=i+1
            else:
                nums[j+1]=nums[i]
                i=i+1
                j=j+1
        a=nums[:j+1]
        print(a)
        return(j+1)

关键：这道题用到了两个指针，去掉了O(N)的空间复杂度。