408-数据结构-顺序表删除相同元素

王道书习题2.2.3 应用题05

题目：从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

算法步骤：

初始化检查: 如果数组为空，则直接返回。
索引初始化: index 用于记录存放不同元素的位置，初始化为0。
遍历数组: 从数组的第二个元素开始，逐个检查当前元素是否与前一个不同。如果不同，则将index加1，并将当前元素赋值到index位置。
调整数组大小: 使用resize方法将数组大小调整为index + 1，从而删除多余的重复元素。
输出结果: 最后，遍历并输出处理后的数组。

这个算法的时间复杂度为O(n)，其中n是数组的大小。由于是对原数组进行操作，空间复杂度为O(1)。

代码：

void delSame(vector<int>& arr){
    if (arr.empty()){
        return;
    }
    int i,j;
    for (i = 0,j = 1; j < arr.size(); j++) {
        if (arr[i]!=arr[j]){
            i++;
            arr[i] = arr[j];
        }
    }
    arr.resize(i+1);//当你希望删除容器末尾的元素时，可以使用 resize 来缩小容器的大小。
}

拓展：将本题中的有序表改为无序表，你能想到时间复杂度位O(n)的方法吗？

可以用散列表来实现

在C++中，可以使用哈希表（例如 std::unordered_set）来跟踪已看到的元素

void delSameUnSorted(vector<int>& arr){
    std::unordered_set<int> seen;
    size_t index = 0;

    for (size_t i = 0; i < arr.size(); ++i) {
        if (seen.find(arr[i]) == seen.end()) {
            seen.insert(arr[i]);
            arr[index++] = arr[i];
        }
    }

    arr.resize(index);  // 调整数组大小，删除多余的元素
}