首页 > itarticle > 26. remove duplicates from sorted array

26. remove duplicates from sorted array

admin 1月 30, 2021 0

Description

Difficulty: Easy

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.

题意:

原地为一个数组去重，返回不重复的数组长度 n 并且仅需保持该数组前 n 位为不重复的数组。

Solution

虽然效率偏低，但是重复的删掉就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
class (object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1:
            return len(nums)
        elif len(nums) == 2:
            if nums[0] == nums[1]:
                return 1
            else:
                return 2
                
        
        i = 1
        while i < len(nums):
            # if nums[tail] != nums[i]:
            #     tail += 1
            if nums[i-1] == nums[i]:
                del(nums[i])
            else:
                i += 1
        return len(nums)

update：
讨论中展示了一种简洁而优美的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
class :
    # @param a list of integers
    # @return an integer
    def removeDuplicates(self, A):
        if not A:
            return 0
        newTail = 0
        for i in range(1, len(A)):
            if A[i] != A[newTail]:
                newTail += 1
                A[newTail] = A[i]
        return newTail + 1

也就是将每一个不同的元素复制到 newTail 位置。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能