我有一个排序的整数列表，我希望在常数时间内将任何元素插入到这个列表中。我可以做一些预处理，只要它能让我在恒定时间内运行这个操作(即，无论我在预处理后重复这个操作多少次，它都应该在恒定时间内运行)。
如何做到这一点？
编辑:我可以想到更多的约束来减少歧义，并且解决起来更具挑战性 -
- 列表需要在插入后按排序顺序维护
- 或者，列表需要以某种方式支持插入后恒定时间的最大/最小操作。
最佳答案
您可以将整数放入 radix tree 中，将整数视为位串。使用基数 2 和 32 位整数列表，您将拥有最大树深度 32，这是恒定时间插入的常数因子(您通常不会这样做，因为基数树可能会比平衡二叉树的对数因子大，再加上你需要为基数树做的所有位操作都将是昂贵的)
关于algorithm - 在恒定时间内插入到排序列表中，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26351651/