已知长度为n的有序线性表a采用顺序存储结构,设计一个时间复杂度为o(n)、空间复杂度为o(1)的算法,该算法删除线性表中所有值为item的数据元素。
时间: 2023-04-28 17:02:25 浏览: 230
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)
算法步骤如下:
1. 定义两个指针i和j,初始值都为。
2. 从头开始遍历线性表a,当a[i]不等于item时,将a[i]赋值给a[j],同时i和j都加1。
3. 当a[i]等于item时,i加1,跳过该元素。
4. 遍历完整个线性表后,将j的值作为新的线性表长度。
5. 时间复杂度为O(n),空间复杂度为O(1)。
代码实现如下:
void delete_item(int a[], int n, int item)
{
int i, j;
for (i = , j = ; i < n; i++) {
if (a[i] != item) {
a[j] = a[i];
j++;
}
}
n = j;
}
阅读全文