## 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

- the answer must be less than or equal 6.
- any number larger than 6 can be treated the same as 6.
- record 2 number: flag and ret. which means there are 'flag' nums greater than 'ret + 1'
- 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);
}
};
```