# 12 line of C++ code, O(n), 0.00012s execution time!!! (3 solutions inside)

• ## my best solution as described in the title

`````` class Solution {
public:
int cycle(vector<int>& citations){
// there are 'flag' nums greater than 'ret + 1'
int ret = 0, flag = 0, size = citations.size();
int record[size + 1];
memset(record, 0, sizeof(record));
for (int i = 0; i < size; ++i){
int cur = citations[i];
if (cur >= size) record[size]++;
else record[cur] += 1;
if (cur <= ret) continue;
if (++flag < ret + 1) continue;
flag -= record[++ret];
}
return ret;
}

int hIndex(vector<int>& citations) {
for (int i = 0; i < 99; ++i) cycle(citations);
return cycle(citations);
}
};
``````

Since the execution time is so fast, I wrap it with a 100 times cycle.
While it still only needs 12ms time.

several tips to consider:
let's assume the total num of vector is 6

1. the answer must be less than or equal 6.
2. any number larger than 6 can be treated the same as 6.
3. record 2 number: flag and ret. which means there are 'flag' nums greater than 'ret + 1'
4. iterate the vector once, and the ret is what the solution is.

##here I provide another 2 solutions:

### second solution:

the second solution is the same idea with the first but I use `unordered_map`, which takes much more time of 2.56ms:

``````class Solution {
public:
int cycle(vector<int>& citations){
// there are 'flag' nums greater than 'ret + 1'
int ret = 0, flag = 0;
unordered_map<int, int> uii;
for (int i = 0; i < citations.size(); ++i){
int cur = citations[i];
uii[cur] += 1;
if (cur <= ret) continue;
if (++flag >= ret + 1){
++ret;
flag -= uii[ret];
}
}
return ret;
}

int hIndex(vector<int>& citations) {
for (int i = 0; i < 99; ++i) cycle(citations);
return cycle(citations);
}
};
``````

### the third solution:

it sorts the vector first. time complexity of O(n*logn), it is faster than the second(1.16ms), amazing!

``````class Solution {
public:
int cycle(vector<int>& citations){
sort(citations.begin(), citations.end());
int i = citations.size() - 1;
for (; i >= 0; --i){
int c = citations.size() - i;
if (citations[i] < c) break;
}
return citations.size() - 1 -i;
}

int hIndex(vector<int>& citations) {
for (int i = 0; i < 99; ++i) cycle(citations);
return cycle(citations);
}
};``````

• Hi, your algorithm1 is good! But a bit obscure to understand, at least to me. Based on your idea, I rewrote one with Bucket sorting, for easier reading for others.

``````class Solution {
public:
int hIndex(vector<int>& citations) {
auto size = int(citations.size());
vector<int> buckets(size + 1);

for (auto d: citations) {
buckets[min(d, size)] += 1;
}

for (int p = size - 1; p >= 0; --p) {
buckets[p] += buckets[p + 1];
}

int ret = 0;
for (int p = size; p >= 0; --p) {
ret = max(ret, min(p, buckets[p]));
}

return ret;
}
};
``````

• This one is a lot more friendly to me. Is it equivalent to original algorithm 1? For ret=max(ret, min(p, buckets[p])), do we have to loop from size to 0?

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