官方题解｜删除元素使数组去重

题目解析

本题数据范围比较小，做法很多。这里使用一种时间复杂度较小，且通用的方法。

我们从后到前考虑整个数组中的元素，不断将元素添加至集合中，直至某个元素已经在集合中出现过。

此时数组中剩下的未被遍历的元素数量即为最小操作次数。

此方法时间复杂度 $\mathrm{O}(N\log{N})$。

AC代码

#include <bits/stdc++.h>

int main() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (auto &x : a) std::cin >> x;
    std::set<int> st;
    while (!a.empty() and !st.count(a.back())) {
        st.insert(a.back());
        a.pop_back();
    }
    std::cout << a.size() << '\n';
    return 0;
}