richenyunqi's blog

By richenyunqi, history, 4 years ago, In English

For question F. Equalize the Array, if I submit the code using unordered_map as follows, it will get TLE:

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
gg ni, mi, ti, ki, di, pi;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // ti
    cin >> ti;
    while (ti--) {
        cin >> ni;
        unordered_map<gg, gg> um;
        for (gg i = 0; i < ni; ++i) {
            cin >> mi;
            um[mi]++;
        }
        vector<gg> v;
        for (auto& [i, j] : um) {
            v.push_back(j);
        }
        sort(begin(v), end(v));
        gg ans = 0, n = v.size();
        for (gg i = 0; i < n; ++i) {
            if (i > 0 and v[i] == v[i - 1]) {
                continue;
            }
            ans = max(ans, v[i] * (n - i));
        }
        cout << ni - ans << "\n";
    }
    return 0;
}

However, if I submit the code using map as follows, it will be accepted:

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
gg ni, mi, ti, ki, di, pi;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // ti
    cin >> ti;
    while (ti--) {
        cin >> ni;
        map<gg, gg> um;
        for (gg i = 0; i < ni; ++i) {
            cin >> mi;
            um[mi]++;
        }
        vector<gg> v;
        for (auto& [i, j] : um) {
            v.push_back(j);
        }
        sort(begin(v), end(v));
        gg ans = 0, n = v.size();
        for (gg i = 0; i < n; ++i) {
            if (i > 0 and v[i] == v[i - 1]) {
                continue;
            }
            ans = max(ans, v[i] * (n - i));
        }
        cout << ni - ans << "\n";
    }
    return 0;
}

As you can see, there is only one difference between these two codes: one uses unordered_map, and another uses map. But the result is different. Why?

  • Vote: I like it
  • -27
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

unordered map worst case complexity is more!!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

unordered map worst case complexity is $$$O(n*n)$$$ whereas for map it's $$$O(logn)$$$. This is because unordered map is based on hashing where multiple numbers can be hashed to same value forming large chains giving worse case search complexity $$$O(n)$$$.