假设您得到一个已经排序的整数列表，例如 (1,7,13,14,50)。应该注意的是，该列表将不包含重复项。
是否有一些数据结构可以存储它，同时允许我在恒定时间内添加任何新元素(在适当的位置)？ add(10) 会产生 (1,7,10,13,14,50)。
同样，我是否能够更新一个元素(例如将 7 更改为 19)并在恒定时间内相应地改变顺序？变化 (7,19) 产生 (1,13,14,19,50)。
对于一个类，我需要编写一个数据结构来尽快执行这些操作，但我只想知道是否可以完成恒定时间，如果不能，那么理想的运行时间是什么？
最佳答案
要以恒定时间 O(1) 插入，这只会作为任何数据结构的最佳情况发生。哈希表通常具有最佳插入时间，但如果存在冲突并且存在单独的链接，它可能并不总是 O(1)。您不对哈希进行排序，因此复杂性无关紧要。
二叉树有很好的插入时间，作为奖励，它在插入新节点时已经排序。然而，这平均需要 O(logn) 时间。如果树为空，则插入的最佳情况是 O(1)。
这些只是几个示例，有关这些操作的复杂性的更多信息，请参见此处:http://bigocheatsheet.com/
关于java - 是否可以在恒定时间内添加/更新排序列表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40116694/