如何优化数组去重计数代码以通过CSES测试用例（解决超时）

问题原因 #

你的代码使用unordered_set统计不同元素个数，虽然平均时间复杂度为O(n)，但最坏情况下插入操作的时间复杂度会退化为O(n)（比如哈希冲突严重时，底层结构退化成链表）。当测试用例数据规模接近题目上限（如n=2×10^5），这种最坏情况会导致总运行时间超出限制。

优化方案 #

推荐使用排序+去重的方法，时间复杂度稳定在O(nlogn)，实际运行效率更可靠，完全适配大数据量场景：

优化后的代码（手动去重） #

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    cin >> n;
    vector<ll> nums(n);
    
    for(ll i=0; i<n; i++) {
        cin >> nums[i];
    }
    
    sort(nums.begin(), nums.end());
    ll count = 1;
    for(ll i=1; i<n; i++) {
        if(nums[i] != nums[i-1]) {
            count++;
        }
    }
    
    cout << count << "\n";
    return 0;
}

更简洁的写法（利用unique函数） #

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    cin >> n;
    vector<ll> nums(n);
    
    for(ll i=0; i<n; i++) {
        cin >> nums[i];
    }
    
    sort(nums.begin(), nums.end());
    auto last = unique(nums.begin(), nums.end());
    ll count = last - nums.begin();
    
    cout << count << "\n";
    return 0;
}

方案优势 #

1. C++的sort实现是优化后的内省排序（introsort），实际运行效率极高，稳定的O(nlogn)时间复杂度不会出现性能波动。
2. 去重操作是线性遍历，仅需O(n)时间，整体性能远优于可能遭遇哈希冲突的unordered_set。

若坚持使用哈希表，可尝试给unordered_set指定初始容量（如unordered_set<ll> a(n);）以减少扩容和冲突概率，但仍不如排序方法稳定。

内容的提问来源于stack exchange，提问作者Dhruv Koli