Python里面用什么数据结构代替TreeMap / OrderedMap

在做最近周赛的一个题目

• 1825. Finding MK Average
  

的时候想到这个问题：

• 当题目需要用到sorted map / list，比如带有Ordered Map标签的题目，python玩家应该用什么代替？（增删操作都是O(logn)时间，并且不会退化到O(n)）
  

Build-in package：Python本身built-in package里面没有类似Java的TreeMap，也没有红黑树或者balanced BST。如果自己写一个简单的BST，在worst case时候又不够快。而且在面试时候，也没有必要当场写一个AVL Tree出来吧。

Python Sorted Containers：看Leetcode讨论区很多人在用Python Sorted Containers 这个package 里面的SortedList / SortedDict。刷题的时候的确是很好用，但是如果面试的时候直接这么用的话，好像题目一下子又变得太简单了，毕竟题目本身就是要我实现这个功能，直接import是不是不符合要求？

Segment Tree： 这类的题目有些是可以用Segment Tree或者Binary Indexed Tree搞定的，但是好像不是一个比较模板的方法。（可能我理解没到位）

大家都是怎么解决的？

acp_ 发表于 2021-5-21 00:28
sortedcontainers 了解一下

很多online平台都不支持第三发库，比如hackerrank，很多公司用来面试笔试。

Leetcode是支持的，刷题很好用，平时工作也没问题，面试不行。

目前没发现有好的解决方法，要么就用性能差的数据结构（可能过不了worst cases），要么只能换语言。。。

如果有哪位大佬知道解决办法，愿闻其详。

望舒 发表于 2021-5-21 07:32
OrderedDict?

OrderedDcit是maintain元素加入时候的顺序，而不是大小顺序

OrderedDict?

同好奇一下

sortedcontainers 了解一下

同问

leyixian 发表于 2021-9-24 19:18
很多online平台都不支持第三发库，比如hackerrank，很多公司用来面试笔试。

Leetcode是支持的，刷题很 ...

我目前的理解是：其实SoretedList也是可以用Segment Tree实现的。Leetcode上面的题目，如果有OrderedMap标签的，讨论区一般也都有Segment Tree / Binary Indexed Tree 的解法。对于不太复杂的题目，往往Binary Search Tree也足够通过了。

幼稚了。写java的人都可以调用treemap, 写python的人用sortedcontainer有啥错？不都是调用api吗？