有序列表插入元素维持排序并去重：高效替代后处理方案探究

直接实现方法：使用bisect模块 #

Python标准库的bisect模块专门用于处理有序序列，正好满足你「插入时维持排序+避免重复」的需求。核心逻辑是：

• 用bisect_left找到元素应插入的位置（保证序列有序）
• 检查该位置的元素是否与待插入元素重复，仅当不重复时执行插入

示例代码：

import bisect

def insert_unique_sorted(lst, num):
    idx = bisect.bisect_left(lst, num)
    # 检查是否越界或元素已存在
    if idx == len(lst) or lst[idx] != num:
        bisect.insort_left(lst, num)
    return lst

测试案例：

# 插入新元素，维持排序
lst1 = [1, 2, 4]
insert_unique_sorted(lst1, 3)  # 返回 [1, 2, 3, 4]

# 插入重复元素，列表不变
lst2 = [1, 3, 4]
insert_unique_sorted(lst2, 3)  # 返回 [1, 3, 4]

封装成专用数据结构 #

如果需要更易用的接口，可以封装一个轻量类：

import bisect

class SortedUniqueList:
    def __init__(self):
        self._data = []
    
    def insert(self, num):
        idx = bisect.bisect_left(self._data, num)
        if idx == len(self._data) or self._data[idx] != num:
            bisect.insort_left(self._data, num)
    
    def get(self):
        return self._data.copy()  # 返回副本避免外部修改内部状态

效率对比：比「append-去重-排序」更高效 #

针对你的场景（结果列表长度<10、多数插入失败、10^6次函数调用），bisect方案的优势非常明显：

1. 插入失败的情况：仅需bisect_left的O(log n)次比较（n<10时仅3-4次），无需任何修改操作；而常规方法要执行append→转集合→排序，即使元素重复也要完成全部步骤，排序的O(n log n)操作（n=10时约30次操作）累计10^6次会产生大量额外开销。
2. 插入成功的情况：bisect.insort_left的插入操作是O(n)（移动元素），但n<10时移动成本极低；常规方法同样需要转集合和排序，开销仍大于bisect方案。

整体来看，bisect方案的单次操作耗时远低于常规方法，10^6次调用的累计性能差距会非常显著。

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