public int hIndex(int[] citations) {
int len = citations.length;
int[] count = new int[len + 1];
for (int c: citations)
if (c > len)
count[len]++;
else
count[c]++;
int total = 0;
for (int i = len; i >= 0; i) {
total += count[i];
if (total >= i)
return i;
}
return 0;
}
A Clean O(N) Solution in Java

Great
O(n)
code! I rewrite it in C++ :)class Solution { public: int hIndex(vector<int>& citations) { int n = citations.size(), h = 0; int* counts = new int[n + 1](); for (int c : citations) counts[min(c, n)]++; for (int i = n; i; i) { h += counts[i]; if (h >= i) return i; } return h; } };

Another way to handle the 2nd loop in C#.
public int HIndex(int[] citations) { int[] counts = new int[citations.Length + 1]; for(int i = 0; i < citations.Length; i++) if(citations[i] >= citations.Length) counts[citations.Length]++; else counts[citations[i]]++; for(int i = 0, countRight = citations.Length; i < counts.Length; i++){ if(countRight <= i) return countRight; countRight = counts[i]; if(countRight <= i) return i; } return 0; }

@tianyicai2010 Actually there should be only one solution, if I am not wrong. Suppose there are two different results
a
andb
anda < b
inn
citations: First, as for b, there are
b
citations that are bigger or equal tob
.  Second, as for a, there are
a
citations that are bigger or equal toa
and the restna
citations are equal to or less thana
;  But, since
b>a
then there are at leastb
citations that are bigger thana
(according to the First) and then at most there will benb
that are less than or equal toa
which is a contradiction against the fact that there will bena
that is equal to or less thana
(according to the Second).
@administrators Am I right? If so, I think the description of the problem should be corrected A.S.A.P. Thank you! @1337c0d3r
 First, as for b, there are

This question is not easy to understand to me. First we come to
1) The easier solution which given by the wiki page:First we order the values of f from the largest to the lowest value.
Then, we try to find thelast
number>=
its index, its index is the Hindex.For example, if we have a researcher with 5 publications:
25, 8, 5, 3, 3
citations respectively,
1 , 2, 3, 4, 5
as index.The number is 5, Hindex is 3.
2) The O(n) solution:
A researcher have 5 pulications:
A, B, C, D, E
with
5, 8,10, 4, 3
citation respectively.After first loop:
for (int c: citations) if (c > len) count[len]++; else count[c]++;
we have the count array:
value: 0, 0, 0, 1, 1, 3 index: 0, 1, 2, 3, 4, 5
In second loop:
for (int i = len; i >= 0; i) { total += count[i]; if (total >= i) return i; }
Step 1: index is 5, total = 3.
Step 2: index is 4, total = 4, return 4.