Remove Duplicates from Sorted Array

发表于 | 分类于

[Leetcode] Remove Duplicates from Sorted Array

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:

1
2
3
4
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.

解题思路
该题除了要求计算出不重复的数字长度外，还要返回一个不重复的数组，且不能增加额外的存储空间。第一个想法是，一边遍历一边把重复的数字从数组中删去。由于for循环中删除数组，index仍然会增加，所以用一个自定义的index（n）去遍历数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums == None or len(nums) == 0:
            return 0
        i = None
        l = 0
        n = 0
        while n < len(nums):
            if i == nums[n]:
                nums.remove(nums[n])
                # continue
            else:
                i = nums[n]
                l +=1
                n+=1
        return l

这个方法提交之后，运行时间较长，看了大神的代码。他们不使用remove操作，因为这个操作用时较长，使用替换的方法。用两个标记，一个记录当前数组中遍历的位置，一个是新数组的位置，当两个位置的值一样时说明有重复，则当前数组位置+1，如果不一样，则新数组位置的值等于当前数组位置的值，更新新数组。

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
        """
		 tail = 0
        if not nums:
            return 0
        for i in range(1, len(nums)):
            if nums[i] != nums[tail]:
                tail += 1
                nums[tail] = nums[i]
        print nums
        return tail + 1