已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

时间复杂度为O(n)、空间复杂度为O(1)的算法，可以采用类似快排的思想，遍历整个线性表，将不等于item的元素移到表头，最后将表的长度减去移动的元素个数即为删除元素后的线性表长度。

具体实现如下：

void DeleteItem(SeqList &L, int item)
{
    int count = 0; // 记录移动元素的个数

    for(int i = 0; i < L.length; i++)
    {
        if(L.data[i] != item)
        {
            L.data[i - count] = L.data[i];
        }
        else
        {
            count++;
        }
    }

    L.length -= count;
}

其中，SeqList 是顺序表的结构体，定义如下：

#define MAX_SIZE 100

typedef struct
{
    int data[MAX_SIZE];
    int length;
} SeqList;

这个算法遍历了整个线性表，时间复杂度为O(n)，并且只使用了常数个辅助变量，空间复杂度为O(1)。

相关问题

已知长度为n的线性表a采用顺序存储结构，请写一时间复杂度为o(n)、空间复杂度为o(1)的算法，该算法删除线性表中所有值为item的数据元素

算法如下：

1. 定义两个指针i和j，初始值都为1。

2. 从头开始遍历线性表a，如果a[i]不等于item，则将a[i]赋值给a[j]，同时i和j都加1。

3. 如果a[i]等于item，则i加1，跳过该元素。

4. 遍历完整个线性表后，将长度设置为j-1。

时间复杂度为O(n)，空间复杂度为O(1)。

已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 O(n)、空间复杂度为 O(1)的算法，该算法删除线性表中所有值为 item 的数据元素。

可以使用双指针法，一个指针指向当前需要删除的元素，另一个指针指向下一个不需要删除的元素。具体实现如下：

1. 初始化两个指针 i 和 j，i 指向第一个元素，j 指向第二个元素。
2. 从头到尾遍历线性表，如果 A[i] 不等于 item，则将 A[i] 复制到 A[j]，同时 i 和 j 同时向后移动一位；如果 A[i] 等于 item，则只移动 i。
3. 最后将线性表的长度更新为 j，即可完成删除操作。

时间复杂度为 O(n)，空间复杂度为 O(1)。