已知长度为n的线性表A采用顺序存储结构,请写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法可删除线性表中所有值为item的数据元素。
时间: 2023-05-11 22:03:08 浏览: 105
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)
可以使用双指针法,一个指针指向当前遍历到的元素,另一个指针指向当前已删除元素的位置。遍历整个线性表,如果当前元素不等于item,则将其复制到已删除元素的位置,并将已删除元素的位置向后移动一位。最后返回已删除元素的位置即可。
以下是示例代码:
void deleteAll(int A[], int n, int item) {
int i, j = 0;
for (i = 0; i < n; i++) {
if (A[i] != item) {
A[j] = A[i];
j++;
}
}
return j;
}
阅读全文