Я столкнулся с этой проблемой кодирования, и мне трудно найти решение.
Учитывая массив целых чисел, найдите наиболее распространенный элемент в списке целых чисел и верните любое из его индексы случайным образом с равной вероятностью. Решение должно выполняться за время O (N) и использовать пространство O (1).
Пример:
List contains: [-1, 4, 9, 7, 7, 2, 7, 3, 0, 9, 6, 5, 7, 8, 9]
7 is most common element so output should be one of: 3, 4, 6, 12
Теперь эта проблема была бы довольно тривиальной, если бы не постоянная ограниченность пространства. Я знаю, что отбор проб из пласта может быть использован для решения проблемы с этими ограничениями, если мы заранее знаем самый распространенный элемент. Но если мы не знаем наиболее распространенный элемент, как эта проблема может быть решена?