Remove Duplicates from Sorted Array

26. Remove Duplicates from Sorted Array

Given a sorted array nums, 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.

输入是一个排序好的数组, 我们需要去掉所有重复的元素, 然后返回这个数组的长度. 值得注意的是, 题目还要求: 1. 不能使用额外的空间. 2. 需要in-place修改

思路

这题没有什么思路可以讲的, 非常直观. 从 index = 1开始遍历数组, 当nums[i] == nums[i-1]的时候, 把nums[i]从数组当中删去.

Code

def removeDuplicates(nums):
    i = 1
    while i < len(nums):
        if nums[i] == nums[i-1]:
            nums.pop(i)
        else:
            i += 1
    return len(nums)

时间复杂度

$O(n)$