Войти Регистрация
Алгоритмы

207. Коды неисправностей чаще чем в трети отчётов

Средняя

Банкоматы Сбера присылают отчёты, в каждом — числовой код неисправности: codes[i].

Верните по возрастанию все коды, которые встречаются строго больше чем в n / 3 отчётов. Решите за один-два прохода и O(1) дополнительной памяти: контроллер на устройстве не держит словарь на все коды.

В работе: Сервисный инженер едет с запчастями под самые частые неисправности: за сутки устройство пишет до 50 000 отчётов, а памяти у контроллера — килобайты.

Пример 1

Ввод
codes = [504, 17, 504, 230, 17, 504, 17]
Вывод
[17, 504]

504 и 17 — по три раза из семи, 3 > 7/3.

Пример 2

Ввод
codes = [1, 2, 3]
Вывод
[]

Каждый ровно треть — не больше трети.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • 0 ≤ codes[i] ≤ 10⁹
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def frequent_faults(codes):
Голосование Бойера — МураМассивПодсчётцельO(n)

Источник: наша задача на данных Сбера. Условие пересказано своими словами.