python - 在 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() function :

   bisect.insort(L, X)
   

2. L.remove(X) 将扫描整个列表，直到找到 X。使用 del L[bisect.bisect_left(L, X)] 代替(前提是 X 确实在 L 中)。

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