c++STL的algorithm中unique函数去重数组

在C++ STL的algorithm库中，unique函数可以用于去除数组中的重复元素。unique函数不会改变数组的大小，而是将重复的元素移到数组的后面，并返回一个新的结束迭代器，表示不重复元素的范围。

下面是使用unique函数去重数组的示例：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 2, 3, 4, 4, 4, 5};

    // 先排序，以便 unique 可以正确地处理重复元素
    std::sort(vec.begin(), vec.end());

    // 使用 unique 去除重复元素
    auto it = std::unique(vec.begin(), vec.end());

    // 使用 erase 去除多余的元素
    vec.erase(it, vec.end());

    // 输出去重后的数组
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }

    return 0;
}

运行上述代码，将会得到以下输出：

1 2 3 4 5

解释

1. 排序：std::sort(vec.begin(), vec.end()); 先对数组进行排序。unique函数只能移除连续的重复元素，因此在使用unique函数之前需要先对数组进行排序。

2. 去重：auto it = std::unique(vec.begin(), vec.end()); unique函数将相邻的重复元素移到数组的末尾，并返回一个指向新末尾的迭代器。

3. 删除多余元素：vec.erase(it, vec.end()); 使用erase函数删除unique函数移动到末尾的多余元素，以调整数组的大小。

这种方法的时间复杂度为O(N log N)，其中N是数组的大小。主要的时间花费在排序上，而unique和erase的时间复杂度都是线性的，即O(N)。