如何快速使用只有一个更改值的列表?

如果列表已排序,您只需从列表中删除要更改的元素,更改后,您就可以“二进制插入”它,不是吗?平均需要对数(n)步。

如果可以,请将数组更改为java.util.TreeMap:删除和插入都将是日志(n)操作:这将比使用阵列的O(1)access+O(n)重新插入解决方案更快。

根据新值是大于还是小于上一个值,您可以将其“气泡化”到位。

伪代码如下所示:

if new value larger than old value
    then if new value is larger than next value in collection
        then swap the value with the next value
        iterate until value is not larger than next value
else if new value is smaller than previous value in collection
    then swap the value with the previous value
    iterate until value is not smaller than the previous value

首先,在集合中找到元素应该位于的新位置。然后,将元素移动到位。如果新的点索引大于当前点索引,则将元素下移一个元素,否则将元素上移。将元素从先前占用的点移动到要占用的点。然后将值存储到找到的位置。

例如,假设此集合:

 a   b   c   d   e   f   g   h   i    j
10  20  30  40  50  60  70  80  90  100

然后要将f元素的值从60更改为95。

 a   b   c   d   e   f   g   h   i    j
10  20  30  40  50  60  70  80  90  100
                                   ^
                                   +- here

 a   b   c   d   e   f   g   h   i    j
10  20  30  40  50  60  70  80  90  100  <-- from this
10  20  30  40  50  70  80  90  ??  100  <-- to this

然后将值存储到??空间,给你这个阵型

 a   b   c   d   e   g   h   i   f    j
10  20  30  40  50  70  80  90  95  100

如果列表确实很大,并且需要大量的更新操作,那么简单的随机访问数组或链表将太慢。如果使用数组/链表,则每次更新操作的成本为O(n)。对于小列表和/或少量更新,这就足够了。

对于较大的列表,可以通过使用排序的O(log(n))数据结构(AVL/RB树、跳过列表、段树等)来实现O(log(n))更新。一个简单的实现可以包括删除要更新的元素,更改值,然后重新插入它。许多流行语言在它们的库中有某种排序的数据结构(例如java中的TeMePa/TeSeSET,C++中的多集/多点STL),或者您可以很容易地找到一种对语言的自由实现。

将列表中未排序的元素向左或向右移动似乎是最佳解决方案

对于一个数组,将一个元素插入到正确的位置将是O(n),因为您需要复制数组元素来为一个额外的元素腾出空间。您可以通过执行 binary search (O(logn))或 linear search

很快 binary search tree self-balancing binary search tree 为确保这一点,或希望您的数据不会以高度规则的顺序插入,以接近O(logn)

方式

您可以只做一次冒泡排序的迭代:从列表的开头开始,迭代直到找到无序元素。然后向适当的方向移动它,直到它落到位。这将给你最坏的2N性能。

删除一个项目,并重新添加到正确的位置。 如果 你只做了一个项目,你的最大运行时间是N。