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()功能：

   bisect.insort(L, X)
   

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

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

Answer 2

您可以使用 Raymond Hettinger 的IndexableSkiplist。它及时执行3个操作O(ln n)：

• 插入值
• 移除价值
• 按等级查找值

---

import skiplist
import random
random.seed(2013)

N = 10
skip = skiplist.IndexableSkiplist(N)
data = range(N)
random.shuffle(data)
for num in data:
    skip.insert(num)

print(list(skip))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for num in data[:N//2]:
    skip.remove(num)

print(list(skip))
# [0, 3, 4, 6, 9]