LeetCode 解题报告 (26)-- 消除有序数组中重复值 (常数空间)

发表于 标签 ，

原题如下：
>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.

题目不难理解，但是要注意的是除了返回 length 以外，对原来数组的元素也要处理，因为 LeetCode 的评测是根据你给出的 length 去读取原来数组的前 length 个元素。

注意题目要求的空间复杂度是常数，这意味着不能新建一个数组来存放不重复元素。

实现思路是双指针，就是先用一个整数 count 来维护已经选出的不重复的元素的个数，同时 count 也作为数组下标。然后另外一个指针遍历数组，找到与当前数组下标为 count 的元素不重复的元素，交换两者即可。

因为数组已经排列了，所以后面的元素肯定会比前面的要大。所以假如给出的数组是无序的同时要实现这个功能，那么可以先排序再使用上面的方法。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):  
    def removeDuplicates(self, nums):  
        """  
        :type nums: List[int]  
        :rtype: int  
        """  
        if len(nums) <= 1:  
            return len(nums)

        count = 0  
        for i in range(1,len(nums)):  
            if not nums[i] == nums[count]:  
                count+=1  
                nums[count]=nums[i]  
        return count+1