H-Index

Средняя№274поиск по ответу

Даны числа цитирований статей одного учёного. Его индекс Хирша — наибольшее h, при котором у h статей не меньше h цитирований у каждой. Нужно его найти. Наш пример: [6, 0, 3, 11, 1, 5] — ответ 3: у четырёх статей не меньше 3 цитирований, а не меньше 4 — только у трёх.

274 H-IndexРазбор · 1×

Пример: Цитирования [6, 0, 3, 11, 1, 5], не отсортированы. Верхний ряд — возможные h, 0..6; ниже — статьи, которые считаем для h = mid.

возможные h0123456loцитирования6031115count—
h ещё возможносередина, проверяемстатья, у которой не меньше mid цитированийотброшеноиндекс Хирша

h = 0 подходит всегда: lo = 0

01/19
сначала · назад · пуск · шаг
Скорость
1function hIndex(citations):
2 lo = 0
3 hi = len(citations) // h <= the number of papers
4 while lo < hi:
5 mid = ceil((lo + hi) / 2) // round up
6 count = papers with at least mid citations
7 if count >= mid:
8 lo = mid // h = mid works: keep it
9 else:
10 hi = mid - 1
11 return lo
состояние
lo
0
hi
–
mid
–
count
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Если у h статей не меньше h цитирований у каждой, то подходит и любое меньшее h. Поэтому по h = 0, 1, 2, … проверки идут «да, …, да, нет, …, нет», а ответ — последнее «да».
  2. Поиск идёт по ответу h, а не по массиву, поэтому цитирования сортировать не нужно: каждая проверка просто считает статьи, у которых не меньше mid цитирований.
  3. lo = mid оставляет подходящее h, поэтому mid округляем вверх. С округлением вниз при lo = 3 и hi = 4 снова вышло бы 3, и диапазон перестал бы сужаться.

Сложность

Время O(n log n): пробуем около log n значений h, и каждый подсчёт проходит по всем n статьям. Память O(1). Подсчёт статей по числу цитирований даёт O(n), но здесь показан паттерн.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.