C++ 算法设计：顺序表删除元素 (空间复杂度 O(1))

本教程展示了如何在 C++ 中使用空间复杂度为 O(1) 的算法从顺序表中删除所有值为 x 的元素。

算法伪代码

1. 初始化变量 i 为 0
2. 从第 0 个位置开始，遍历顺序表中的每个元素
3. 如果当前元素值等于 x，则将 i 自增 1，即跳过该元素
4. 否则，将第 i 个元素的值替换为当前元素的值，并将 i 自增 1
5. 重复步骤 2~4，直到遍历完所有元素
6. 修改顺序表的长度为 i

C++ 源代码

#include <iostream>
using namespace std;

void deleteElements(int arr[], int& n, int x) {
    int i = 0;
    for (int j = 0; j < n; j++) {
        if (arr[j] != x) {
            arr[i] = arr[j];
            i++;
        }
    }
    n = i;
}

int main() {
    int arr[] = {1, 2, 3, 4, 3, 5, 6, 3, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;

    cout << '原始顺序表：';
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' '; 
    }
    cout << endl;

    deleteElements(arr, n, x);

    cout << '删除元素' << x << '后的顺序表：';
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' '; 
    }
    cout << endl;

    return 0;
}

输出结果

原始顺序表：1 2 3 4 3 5 6 3 7 
删除元素 3 后的顺序表：1 2 4 5 6 7

算法原理：

该算法利用了原地修改顺序表的方法，通过一个指针 i 来记录新顺序表的末尾位置。遍历原顺序表，对于不等于 x 的元素，将其复制到 i 所指的位置，并将 i 自增 1。最后修改顺序表的长度为 i，即删除所有值为 x 的元素。

空间复杂度分析：

该算法只使用了一个指针 i，空间复杂度为 O(1)，满足题意。