H-индекс

Постановка задачи

citations = [3, 0, 6, 1, 5]

3

citations = [1, 3, 1]

1

Решение

В этой задаче сортировка помогает превратить определение H-индекса в простой проход по массиву. Нам нужно найти максимальное число h, для которого существует хотя бы h статей с количеством цитирований не меньше h.

Если отсортировать цитирования по возрастанию, то для каждого индекса i мы можем заметить важный факт: справа от i, включая сам i, находится n - i статей, и каждая из них имеет не менее citations[i] цитирований.

Идея решения:

Отсортируем citations по возрастанию. Затем пойдем слева направо. Для каждой позиции i посчитаем:

h = n - i

Это количество статей, которые находятся справа от i и имеют цитирований не меньше citations[i].

Если citations[i] >= h, значит, у нас есть как минимум h статей, каждая из которых имеет не менее h цитирований. Поскольку мы идем слева направо, первое такое h будет максимально возможным.

Почему первое найденное значение максимальное? В начале прохода h максимально и равно n. Затем h уменьшается на 1 на каждом шаге. Как только условие становится истинным, мы нашли самый большой H-индекс.

Основные шаги:

1. Сортируем citations по возрастанию.
2. Идем по индексам от 0 до n - 1.
3. Для каждого индекса считаем h = n - i.
4. Если citations[i] >= h, возвращаем h.
5. Если такого индекса нет, возвращаем 0.

Рассмотрим пример:

citations = [3, 0, 6, 1, 5]

После сортировки:

citations = [0, 1, 3, 5, 6]

Проверяем позиции:

1. i = 0, h = 5, citations[i] = 0. Условие не выполняется.
2. i = 1, h = 4, citations[i] = 1. Условие не выполняется.
3. i = 2, h = 3, citations[i] = 3. Условие выполняется.

Ответ равен 3.

Оценка сложности

Временная сложность

Сортировка массива длины n занимает O(n log n). После этого мы выполняем один проход за O(n).

Итоговая временная сложность: O(n log n).

Пространственная сложность

Если не учитывать память, необходимую для встроенной сортировки, мы храним только несколько переменных. Пространственная сложность составляет O(1).

Код решения

Приведем код решения.

func hIndex(citations []int) int {
    sort.Ints(citations)
    n := len(citations)
    for i := 0; i < n; i++ {
        h := n - i
        if citations[i] >= h {
            return h
        }
    }
    return 0
}

Итоги

Задача H-Index - пример того, как сортировка помогает напрямую связать значение элемента с количеством элементов справа от него.

1. Суть алгоритма: после сортировки по возрастанию для каждого индекса i справа находится n - i статей. Если citations[i] >= n - i, значит, эти статьи дают H-индекс n - i.
2. Эффективность:
   • Временная сложность: O(n log n), потому что основное время занимает сортировка.
   • Пространственная сложность: O(1), если не учитывать память встроенной сортировки.
3. Граничные случаи:
   • Все цитирования равны 0: условие не выполнится ни разу, ответ 0.
   • Одна статья: ответ 1, если у нее есть хотя бы одно цитирование, и 0 в противном случае.
   • Очень большие значения цитирований: H-индекс не может превышать общее количество статей.
4. Сортировка дает простой и понятный способ проверить кандидатов на H-индекс. Первое подходящее значение при проходе слева направо будет максимально возможным.