标签: sortedcontainers

SortedContainers 模块的 SortedList 实现中操作的时间复杂度是多少？据我了解，底层数据结构是数组列表。那么插入是否需要O(n)时间，因为可以找到索引O(logn)然后将元素插入到正确的位置是O(n)？类似地，从索引中弹出元素也必须O(n)如此。

SortedListWithKey可以使用 lambda 函数对列表进行排序：

from sortedcontainers import SortedListWithKey

SortedListWithKey([[4, 'last'], [1, 'first']], key=lambda x: x[0])
# Result: SortedListWithKey([[1, 'first'], [4, 'last']], key=<function <lambda> at 0x107f5d730>)

但是假设我需要使用set()只具有唯一值，文档说它还接受key=参数用于按自定义函数排序，但我无法让它工作：

from sortedcontainers import SortedSet

SortedSet([[4, 'last'], [1, 'first']], key=lambda x: x[0])

会抛出以下异常：

values = set(chain(*iterables))
TypeError: unhashable type: 'list'

有办法实现这一点吗？

from sortedcontainers import SortedDict

d = SortedDict(b=20, d=30, c=10, e=50, a=40)

# What is the time complexity of the following code?
for k, v in d.items():
    print(k, v)

我认为时间复杂度应该是nlog(n)从排序字典中获取条目的成本log(n)，即使我们迭代这个字典，我们基本上执行get操作n次。我的理解正确吗？