# why my O(n) solution is slower than O(nlogn) solution?

• ``````/*
basic idea: counting sort
time: O(n)
space: O(n)
*/
class Solution {
public:
int hIndex(vector<int>& citations) {
unordered_map<int, int> mp;
int n = citations.size();
for (auto i : citations)
mp[min(n, i)]++;
for (int i = n, tmp = 0; i >= 0; i--) {
tmp += mp[i];
if (tmp >= i)
return i;
}
return 0;
}
};
``````

This one takes 8ms.

``````/*
basic idea: sort, then find the biggest square
time: O(nlog(n))
space: O(1)
*/
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(), citations.end());
int n = citations.size(), i = n - 1;
while (i >= 0) {
if (citations[i] < n - i)
return n - i - 1;
i--;
}
return n;
}
};
``````

This one takes 4ms.

• @Tsien Very impressive solution!

As for your problem, `high-level` object in C++ is always inefficient compared to C-way method. So if you change your `map` into an array here, it will be much better 4-ms result.

``````class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
int mp[n+1]{0};
for (auto i : citations)
mp[min(n, i)]++;
for (int i = n, tmp = 0; i >= 0; i--) {
tmp += mp[i];
if (tmp >= i)
return i;
}
return 0;
}
};
``````

• oh, i see. Thank you :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.