如何从有序列表高效获取唯一元素？求复杂度优于O(n)的方案

核心结论 #

对于有序列表的去重操作，不存在时间复杂度优于O(n)的解决方案。因为无论采用何种方法，都必须至少遍历一次列表，才能识别连续重复元素的边界——这是这类问题的理论时间下限，无法突破。

你的思路问题分析 #

你尝试的“隔一个元素检查”思路本身存在逻辑漏洞：连续重复元素的数量可能是奇数或偶数（比如示例中3出现3次），间隔检查会漏掉重复段的边界判断，再加上复杂的条件分支，很容易出现重复添加、漏加元素的问题（比如你的代码在处理[1,1,2,2,3]时会错误添加两次2）。

最优O(n)实现方案 #

既然无法突破O(n)的时间下限，我们可以实现时间O(n)、空间最优的去重逻辑，这已经是这类问题的最优解。以下是两种高效实现方式：

方法1：遍历记录前一个元素（简洁易读）

def get_unique_values(values):
    if not values:
        return []
    unique_list = [values[0]]
    for num in values[1:]:
        # 仅当当前元素与最后一个唯一元素不同时添加
        if num != unique_list[-1]:
            unique_list.append(num)
    return unique_list

方法2：双指针原地修改（空间更优）

如果不需要保留原列表，可以用双指针在原列表上修改，额外空间复杂度为O(1)（除返回结果外）：

def get_unique_values(values):
    if not values:
        return []
    slow_ptr = 0
    for fast_ptr in range(1, len(values)):
        if values[fast_ptr] != values[slow_ptr]:
            slow_ptr += 1
            values[slow_ptr] = values[fast_ptr]
    # 截取到slow_ptr+1的位置，即为所有唯一元素
    return values[:slow_ptr+1]

方案效果验证 #

用你给出的示例列表[1,1,2,3,3,3,6,6,8,10,100,180,180]测试，两种方法都会返回预期结果：[1,2,3,6,8,10,100,180]。

内容的提问来源于stack exchange，提问作者Jack Skyblue