Найти элемент, встречающийся b раз в массиве размера n * k + b
Описание
Для массива размером (n * k + b) где n элементов встречаются k раз, а один элемент встречается b раз другими словами, существует n + 1 различных Элементов. Учитывая, что 0 найдите элемент, встречающийся b раз.
Мои попытки решения
Очевидное решение будет использовать хеширование, но оно не будет работать, если числа очень большие. Сложность составляет
O (n)Использование карты для хранения частот каждого элемента, а затем обход карты для нахождения элемента, встречающегося b раз. Поскольку карты реализованы как деревья со сбалансированной высотой Сложность будет
O (nlogn ).
Оба моих решения были приняты, но интервьюер хотел линейное решение без использования хеширования и намек, который он дал, заключался в том, чтобы сделать высоту дерева постоянной в дереве, в котором вы храните частоты, но я не могу найти правильное решение пока что.
Я хочу знать, как решить эту проблему за линейное время без хеширования?
РЕДАКТИРОВАТЬ:
Пример:
Ввод: n = 2 b = 2 k = 3
Aarray: 2 2 2 3 3 3 1 1
Вывод: 1