问：从顺序表中删除值相同的节点的算法

Xiangbuilder

这个程序的时间复杂度是不是n^3？
有没有可能更小？

rickxbx

n+(n-1)+(n-2)+...+1 是 n^2，有没有好的算法不清楚

Xiangbuilder

从第一个结点开始进行搜索，查找值相同的结点，完了之后，
再从下一个结点开始搜索整个表，查找值相同的结点，
直至最后一个结点，
这样时间复杂度是n^2,

但如果再加上删除的操作，就不止n^2，
顺序表中删除某一个特定结点的时间复杂度是n
所以我觉得时间复杂度最小为n^3，

不知道这个想是不是正确？

rickxbx

不是链表吗？

Xiangbuilder

是顺序表啊。

rickxbx

不好意思，没理解顺序表的意思。一开始只认为了线性表了

kakuyou

如果是大表可能才需要吧。

说个耗内存的方法。

建立原表的index表，进行index快速排序，因为快速排序在最糟的情况下是n的2次方。

然后进行末尾交换，不断的交换最末尾的元素和重合的元素，最后所有值相同的元素就
被放在最后了。