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