leetcode 删除有序数组的重复项

26. 删除有序数组中的重复项

已解答

简单

相关企业

提示

给你一个 非严格递增排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被通过。

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 将数组中的元素转换为集合，自动去除重复元素，然后转换回列表并重新赋值给nums
        # 这一步需要额外的空间，因为集合和列表是不同的数据结构
        nums[:] = sorted(set(nums))  
        # 返回去重后数组的长度
        return len(nums)

set(nums)：将列表nums转换成一个集合。由于集合不允许重复元素，这一步会自动去除数组中的重复项。
sorted(set(nums))：将去重后的集合转换回列表，并对其进行排序。这里假设原数组是有序的，但实际上这一步会重新排序数组，所以原数组的有序性会被破坏。
nums[:] = ...：将排序并去重后的列表重新赋值给nums数组。这里使用nums[:]是为了确保修改原数组，而不是创建一个新的数组。
return len(nums)：返回去重后数组的长度。

需要注意的是，这个解决方案虽然简洁，但它并没有遵循LeetCode题目的要求，即在原地修改数组，不使用额外的空间（空间复杂度为O(1)）。这段代码使用了额外的空间来存储集合和排序后的列表，因此空间复杂度不是O(1)。此外，题目要求保持数组的有序性，但这段代码通过排序破坏了原有的顺序。因此，这个解决方案虽然能够解决问题，但并不是题目要求的最优解。正确的解决方案应该在不使用额外空间的情况下，遍历数组并移除重复项，同时保持数组的有序性。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 初始化k为1，表示新数组（去重后）的索引从1开始
        k = 1
        # 从数组的第二个元素开始遍历，因为第一个元素默认是没有重复的
        for i in range(1, len(nums)):
            # 如果当前元素与前一个元素不同，则说明当前元素是非重复的
            if nums[i] != nums[i-1]:
                # 将当前元素复制到索引为k的位置
                nums[k] = nums[i]
                # k递增，指向下一个可能的非重复元素的位置
                k += 1
        # 返回k的值，即去重后数组的长度
        return k

初始化一个指针k为1，这个指针用来记录去重后数组的长度。
从数组的第二个元素开始遍历，因为题目中提到数组是有序的，所以第一个元素默认是没有重复的。
在遍历过程中，如果发现当前元素与前一个元素不同，说明当前元素是非重复的，需要保留。
将非重复的元素复制到索引为k的位置，然后k递增，指向下一个可能的非重复元素的位置。
遍历结束后，k的值即为去重后数组的长度，返回这个值。

这种方法的时间复杂度为O(n)，其中n是数组的长度，因为它只需要遍历一次数组。空间复杂度为O(1)，因为它不需要额外的存储空间，只是在原数组上进行操作。