Ищет алгоритм для быстрого вычисления h-index

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

Эта страница вики представляет собой определение h-index

в принципе, если бы у меня был массив [0 3 4 7 8 9 10], мой h-индекс был бы 4, так как у меня 4 числа больше 4. Мой h-индекс был бы 5, если бы я был иметь 5 чисел больше 5 и т.д. Если массив целых чисел больше или равен 0, каковы способы эффективного вычисления h-индекса?

edit: массив не обязательно сортируется

Ответ 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;
}

Ответ 2

Это можно сделать в O (n) времени.

Найти медиану массива.
если медианa > (n-1)/2, то число идет до медианы. Найти его итеративно
Если медиана < (n-1)/2, то число приходит после медианы. Найдите его итеративно.
Если медиана == (n-1)/2, то медианой является решение

Здесь я предполагаю, что n нечетно. Немного измените алгоритм для четного n (замените (n + 1)/2 на n/2 при условии, что ранг медианы равен n/2). Кроме того, сложность поиска фактической медианной в O (n) времени. Вместо этого используйте хороший стержень (как в quicksort).

Сложность: n + n/2 + n/4... = O (n)

Ответ 3

Это одно из решений, о котором я мог думать. не уверен, что он лучший.

Сортировка массива в порядке возрастания. сложность nlog (n)

Итерации через массив из индекса от 0 до n. сложность n

и для каждой итерации предположим, что индекс i

if (arr[i] == (arr.length - (i+1))
    return arr[i]

например,

arr =[ 0 3 4 7 8 9 10 ]
arr[2] = 4
i = 2
arr.length = 7
4 = (7- (2+1))

Ответ 4

Меня не устраивала предыдущая реализация, поэтому я заменил ее более быстрым решением, написанным на Java.

public int hIndex(int[] citations) {
    if(citations == null || citations.length == 0)
    {
        return 0;
    }

    Arrays.sort(citations);

    int hIndex = 0;

    for(int i=0;i<citations.length;i++)
    {
        int hNew;

        if(citations[i]<citations.length-i)
        {
            hNew = citations[i];

            if(hNew>hIndex)
            {
                hIndex = hNew;
            }
        }
        else if(citations[i]>=citations.length-i)
        {
            hNew = citations.length-i;

            if(hNew>hIndex)
            {
                hIndex = hNew;
            }

            break;
        }
    }

    return hIndex;
}