python 删除有序数组中的重复项多种解法

编程小白狼

发布于 2024-12-31 08:16:43

4810

使用双指针法，时间复杂度 O(n)，空间复杂度 O(1)。

def removeDuplicates(nums):
    if not nums:  # 如果数组为空，直接返回
        return 0

    i = 0  # 慢指针，用于记录不重复元素的位置
    for j in range(1, len(nums)):  # 快指针，遍历整个数组
        if nums[j] != nums[i]:  # 如果出现不同的元素
            i += 1  # 慢指针加一
            nums[i] = nums[j]  # 将不同的元素放到慢指针所在位置

    return i + 1  # 返回长度

使用 Python 的内置函数 set()，将有序数组转化为集合去重，再转回为列表，时间复杂度 O(n)，空间复杂度 O(n)。

def removeDuplicates(nums):
    nums[:] = sorted(set(nums))  # 将有序数组转为集合去重，再排序后转回为列表
    return len(nums)  # 返回长度

使用 Python 的内置函数 itertools.groupby()，对有序数组进行分组，然后取每组的第一个元素，时间复杂度 O(n)，空间复杂度 O(n)。

import itertools

def removeDuplicates(nums):
    nums[:] = [k for k, _ in itertools.groupby(nums)]  # 对有序数组进行分组，取每组的第一个元素
    return len(nums)  # 返回长度

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-08，如有侵权请联系 cloudcommunity@tencent.com 删除

python