algorithm - 寻找快速计算h-index的算法

Question

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

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

基本上，如果我有一个 [ 0 3 4 7 8 9 10 ] 数组，我的 h-index 将是 4，因为我有 4 个数字大于 4。如果我是，我的 h-index 将是 5有 5 个大于 5 的数字，等等。给定一个大于或等于 0 的整数数组，有哪些有效计算 h-index 的方法？

编辑:数组不一定是有序的

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