寻找快速计算h指数的算法

Question

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

这个维基页面是h-index的定义

基本上如果我有一个[0 3 4 7 8 9 10]的数组,我的h指数将是4,因为我有4个大于4的数字.如果我有5个,我的h指数将是5数字大于5,等等.给定一个大于或等于0的整数数组,有效计算h指数的方法是什么？

编辑:数组不一定排序

Answer 1

在这里我实现O(N)与表格,这是简单和快速:

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;
}