Stable remove zeros через two pointers
Дан vector<int>. Нужно удалить из него все нули так, чтобы относительный порядок остальных элементов сохранился.
Идея на собесе дальше обобщалась до remove_if(begin, end, callback): оставить в начале диапазона элементы, для которых predicate возвращает false, и вернуть итератор на новый логический конец.
В проверках подслучай remove zeros оформлен как Python-функция, которая возвращает компактный список.
Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Подсказки
- Два указателя
read pointer сканирует все элементы, write pointer двигается только после записи ненулевого элемента.
- Порядок
Не сортируйте и не свапайте с концом: это сломает относительный порядок.
Идея решения
Держим индекс write — позицию следующего оставляемого элемента.
Идем по исходному списку слева направо. Если текущий элемент ненулевой, записываем его в values[write] и двигаем write. После прохода все нужные элементы лежат в префиксе values[:write] в исходном порядке.
Эталонный код
def remove_zeros_compact(values: list[int]) -> list[int]:
write = 0
for value in values:
if value != 0:
values[write] = value
write += 1
del values[write:]
return valuesСколько раз value встречается в невозрастающем массиве
Дан отсортированный невозрастающе массив values и число target.
Нужно вернуть, сколько раз target встречается в массиве.
Ожидаемое решение — не линейный проход, а два бинарных поиска:
- найти первую позицию, где элемент
<= target; - найти первую позицию, где элемент
< target; - разность этих позиций и есть количество вхождений.
Сигнатура
def count_occurrences_desc(values: list[int], target: int) -> int:Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Подсказки
- Descending order
Условие для boundary search инвертировано относительно привычного возрастающего массива.
- Две границы
Ищите не один найденный элемент, а левую и правую границу блока target.
Идея решения
В невозрастающем массиве блок значений target лежит между двумя границами.
Первая граница — первый индекс i, где values[i] <= target. Вторая — первый индекс j, где values[j] < target. Тогда все элементы на полуинтервале [i, j) равны target, а ответ равен j - i.
Эталонный код
def count_occurrences_desc(values: list[int], target: int) -> int:
def first_index_where(predicate) -> int:
left = -1
right = len(values)
while right - left > 1:
mid = (left + right) // 2
if predicate(values[mid]):
right = mid
else:
left = mid
return right
first_le = first_index_where(lambda x: x <= target)
first_lt = first_index_where(lambda x: x < target)
return first_lt - first_leИндекс Хирша через подсчет по корзинам
Дан массив неотрицательных целых чисел citations.
Индекс Хирша (H-index) — максимальное такое k, что в массиве есть хотя бы k чисел со значением >= k.
Верните H-index.
Ожидаемое решение для этой версии — O(n) по времени и O(n) по памяти через bucket count. Значения больше n можно класть в bucket n, потому что ответ не может быть больше количества статей.
Сигнатура
def h_index(citations: list[int]) -> int:Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Подсказки
- Верхняя граница
H-index не может быть больше количества статей n.
- Suffix count
При движении справа налево храните число статей с citations >= текущего k.
Идея решения
Пусть n = len(citations). Ответ не может быть больше n, поэтому все значения > n можно считать равными n.
Создаем buckets[0..n], где buckets[i] — сколько статей имеют ровно i цитирований, а buckets[n] также хранит все значения >= n.
Идем по k от n к 0, накапливаем количество статей с citation count >= k. Первый k), где накопленное количество >= k`, и есть H-index.
Эталонный код
def h_index(citations: list[int]) -> int:
n = len(citations)
buckets = [0] * (n + 1)
for citation in citations:
buckets[min(citation, n)] += 1
papers_at_least_k = 0
for k in range(n, -1, -1):
papers_at_least_k += buckets[k]
if papers_at_least_k >= k:
return k
return 0H-index быстрее O(n log n)
Как найти H-index за O(n), почему значения можно обрезать сверху числом статей и что меняется, если разрешено модифицировать входной массив?
Сначала проговорите ответ вслух или тезисами.
Формулы, план решения, риски и примеры.
Откройте разбор только после своей попытки.
Короткий ответ
Для n статей H-index не превышает n. Счётчик bucket[min(citation, n)] и обратная накопительная сумма дают первый k, для которого статей с цитированием не меньше k хотя бы k. Это O(n) по времени и O(n) по памяти.
Подробный разбор
Пусть n — число статей. Значения цитирования выше n эквивалентны для ответа, поэтому каждое citation можно заменить на min(citation, n) и посчитать частоты от 0 до n. Затем идём k от n к нулю и накапливаем число статей с citation ≥ k. Первый k, где накопленная сумма не меньше k, и есть H-index.
Алгоритм использует O(n) времени и O(n) дополнительной памяти. Если вход можно модифицировать и значения позволяют безопасно кодировать счётчики в самом массиве, память можно уменьшить, но такая техника сложнее, чувствительна к переполнению и разрушает данные. Quickselect способен дать ожидаемое O(n), однако доказательство границы и работа с равными значениями сложнее, чем у bucket-решения. На собеседовании сначала стоит дать надёжный линейный вариант.