在Python中插入和删除排序列表

Question

我有一个整数的排序列表,L,我有一个值X,我希望插入到列表中,以便维持L'的顺序.同样,我希望快速找到并删除X的第一个实例.

问题:

1. 如果可能,如何使用bisect模块执行第一部分？
2. L.remove(X)是第二部分最有效的方法吗？Python是否检测到列表已经排序并自动使用对数删除过程？

示例代码尝试:

i = bisect_left(L, y)

L.pop(i)                 #works
del L[bisect_left(L, i)] #doesn't work if I use this instead of pop

Answer 1

1. 你使用的bisect.insort()功能:

   bisect.insort(L, X)
   

2. L.remove(X)将扫描整个列表,直到找到X.del L[bisect.bisect_left(L, X)]改为使用(假设X确实存在L).

请注意,从列表中间删除仍然会产生成本,因为从该位置开始的元素都必须向左移动一步.如果这将成为性能瓶颈,二叉树可能是更好的解决方案.