一道顺序表的简单算法题

来源：百度知道 编辑：UC知道 时间：2024/05/17 20:28:08
已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。(O(1)表示算法的辅助空间为常量)

如题，请给出一个思路即可。我怎么也想不出时间复杂度为O(n)的算法。顺序存储结构不是删除一个元素

就要挪动后面所有元素吗？时间复杂度怎么可能是O(n)呢？

void Purge(struct List *L)
{ int i, j, k;
for ( i = 0; i < L->size; i++ ) {
for ( j = i+1; j < L->size; ) {
if ( L->list[i] == L->list[j] ) {
for ( k = j; k < L->size; k++ ) {
L->list[k] = L->list[k+1];
}
L->size--;
}
else {
j++;
}
}
}
} /* end of Purge */

要是觉得对的话就给我加点分~