已知长度为 n 的线性表 A 采用顺序存储结构,请写一时间复杂度为 O(n)、空间复杂度为 O(1)的算法,该算法删除线性表中所有值为 item 的数据元素。用c++语言写
时间: 2024-10-07 18:02:46 浏览: 2
在 C++ 中,为了在顺序存储的线性表中删除所有值为 `item` 的元素,并保持时间复杂度为 O(n) 和空间复杂度为 O(1),你可以遍历整个列表并在遍历过程中直接跳过或移除对应的元素。这里假设数组 `A` 存储了线性表的内容。
```cpp
#include <iostream>
void deleteAllItems(int A[], int n, int item) {
int i = 0; // 初始化索引为0,表示当前位置
for (int j = 0; j < n; ++j) { // 遍历整个数组
if (A[j] != item) { // 如果当前元素不等于目标值
A[i++] = A[j]; // 将非目标元素移到当前位置并递增索引
}
}
// 索引i现在指向最后一个有效元素的位置,更新n以排除已经移除的部分
n = i;
// 清空剩余部分,因为我们不需要它们
while (i < n) {
A[i++] = 0;
}
}
int main() {
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(A) / sizeof(A[0]);
int item = 5;
std::cout << "Original array:\n";
for (int i = 0; i < n; ++i)
std::cout << A[i] << " ";
deleteAllItems(A, n, item);
std::cout << "\nArray after deleting all items " << item << ":\n";
for (int i = 0; i < n; ++i)
std::cout << A[i] << " ";
return 0;
}
```
在这个例子中,删除操作完成后,`A` 数组中将不会包含任何值为 `item` 的元素。注意,这种方法实际上是改变了原数组的结构,因此并没有创建新的空间。由于我们只用到了常数级别的额外空间,所以空间复杂度为 O(1)。