Python：如何在有序列表中以O(n)获取重复元素及复杂度验证

1. 时间复杂度分析 #

• 第一段代码：仅包含一次遍历数组的for循环，时间复杂度为O(n)，其中n是数组长度。
• 第二段代码：遍历数组的时间复杂度是O(n)，Python中set()的构建时间复杂度是O(k)（k是传入列表的元素个数）。最坏情况下，比如数组全是重复元素，k等于n-1，此时set()的时间复杂度是O(n)。整体时间复杂度为O(n) + O(n) = O(n)，你的理解是正确的。

2. 当前代码的正确性与高效性问题 #

正确性问题 #

• 第一段代码仅适用于每个重复元素恰好出现两次的场景：如果元素出现3次及以上（如[1,1,1]），会将该重复元素多次添加到结果列表中，输出结果会包含多个相同的重复值，不符合“获取去重后重复元素”的需求。
• 第二段代码用set()去重可以得到唯一的重复元素，但set是无序集合，输出顺序可能和原数组中重复元素出现的顺序不一致（比如原数组是[2,2,1,1]，set输出可能是1 2），破坏了原有序列表的顺序特性。

高效性问题 #

两段代码在处理多重复元素时，都会将重复元素多次添加到duplicates列表中（比如[1,1,1,1]会添加3次1），造成不必要的空间浪费，空间复杂度为O(n)（最坏情况）。

3. 正确且高效的实现思路 #

因为输入是有序列表，重复元素必然是连续的，所以可以在遍历过程中直接去重，避免重复添加，同时保持结果的顺序：

• 记录前一个元素，遍历当前元素时，若与前一个相同，且该元素尚未加入结果列表，则添加一次；
• 若当前元素与前一个不同，则更新前一个元素，并重置“是否已添加”的标记。

优化后的代码示例 #

arr = [1, 1, 1, 2, 3, 4, 4, 4, 4, 5]

def get_duplicates(arr):
    duplicates = []
    if not arr:
        return duplicates
    
    prev_num = arr[0]
    has_added = False
    
    for num in arr[1:]:
        if num == prev_num:
            if not has_added:
                duplicates.append(num)
                has_added = True
        else:
            prev_num = num
            has_added = False
    return duplicates

print(*get_duplicates(arr))  # 输出: 1 4

优化点说明 #

• 时间复杂度仍为O(n)，仅需一次遍历；
• 空间复杂度为O(k)，其中k是去重后的重复元素数量，比原代码更节省空间；
• 结果保持原数组中重复元素出现的顺序，符合有序列表的特性；
• 无需额外的set转换操作，逻辑更简洁。

内容的提问来源于stack exchange，提问作者Эмиль Грабчук