26、删除排序数组中的重复项——LeetCode

题目说明

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

具体见官网题目 删除排序数组中的重复项

解题思路

利用集合的特性

第一个思路当然是使用python的集合类型(set)来去掉重复项,list(set(nums)),但是集合类型没有顺序,所以需要再进行一次排序。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        t = list(set(nums))
        length = len(t)
        t.sort()
        for i in range(length):
            nums[i] = t[i]
        return length

由于python按值传递,所以需要依次进行修改,使用一个遍历循环。如果有更好的办法欢迎告诉我。

这样虽然完成了题目的要求,但是使用了额外的空间,空间复杂度为O(m)。所以,下面使用一个通用的算法,与官方答案不谋而合。

迭代法

思路

使用两个指针iji为最后要返回的最后一个元素(即i后面的的都不需要);另一个j用来遍历整个列表或数组,找到与i指向的元素不同的那个元素,并将它移动到i的后面,即i+1的位置。当j遍历到结尾的时候即循环结束,返回i+1i是从0开始的)。

具体实现

int removeDuplicates(int* nums, int numsSize){
    if (numsSize == 1)
        return 1;
    if (!numsSize)
        return 0;
    int i = 0, j = 1;
    while (j < numsSize){
        if (nums[i] != nums[j]){
            nums[i+1] = nums[j];
            i++;
        }
        j++;
    }
    return i+1;
}

优化

此时我们发现,在 j-1==1的时候,我们也同样进行了一次复制移动,这是没有必要的。我们可以加一个判断条件,当 j-i>1的时候才执行复制移动。即

while (j < numsSize){
        if (nums[i] != nums[j]){
            //判断条件
            if (j-i > 1)
                nums[i+1] = nums[j];
            i++;
        }
        j++;
    }

此时,执行时间为28ms。

时间复杂度为O(m),空间复杂度为O(1)。