每日一道LeetCode 1：Array篇--Remove Du

问题：
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 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 new length.

Try 1:

认为既然是sorted array，只用遍历一次array中的每个元素，判断该元素的前一个元素和该元素的后一个元素与该元素不相等即可。当相等时，就删除该元素。

Weakness：
检测到相等元素，动态删除元素后，array剩下的index也发生了变化。遍历会变得混乱

Try 2：

新建一个array，遍历原来的array，如果原来array中的一个元素在新array里不存在，则放入新的array中

weakness：
感觉并没有使用到sorted这个条件，而且新建了一个array，不满足Space: O(1)的条件

Try 3：

在原来的array里面使用两个index，一个index用于遍历整个array，另一个index是要保留的非重复元素的index

# -*- coding: utf-8 -*-
#!/usr/bin/python 

class Solution:
    def removeDuplicates(self, A):
        if not A:
            return 0
        
        newindex, index = 0, 1 
#newindex是不含重复元素的array中的index
#index是用于遍历原来元素的index
        while index < len(A):
            if A[newindex] != A[index]:
                newindex += 1
#如果sorted的元素不重复，则新的array的newindex加1
                A[newindex] = A[index]
#将原来array中不重复的index放入新的newindex下
            index += 1
            
        print A ##输出结果[1,2,2]
        return newindex + 1

if __name__ == "__main__":
    print Solution().removeDuplicates([1, 1, 2])