looking for algorithm to calculate h-index fast

Question

http://en.wikipedia.org/wiki/H-index

this wiki page is a definition of h-index

basically if I were to have an array of [ 0 3 4 7 8 9 10 ], my h-index would be 4 since I have 4 numbers bigger than 4. My h-index would've been 5 if I were to have 5 numbers bigger than 5, and etc. Given an array of integers bigger or equal to 0, what are the ways of calculating h-index efficiently?

edit: the array is not necessarily sorted

Answer 1

Here my realization O(N) with tabling, this is simple and blazing fast:

private static int GetHIndex(int[] m)
{
    int[] s = new int[m.Length + 1];
    for (int i = 0; i < m.Length; i++) s[Math.Min(m.Length, m[i])]++;

    int sum = 0;
    for (int i = s.Length - 1; i >= 0; i--)
    {
        sum += s[i];
        if (sum >= i)
            return i;
    }

    return 0;
}