Число популярно, если оно больше или равно N/4 раза (N - длина массива). Он хотел, чтобы я использовал отсортированные свойство массива и придумать лучшее решение, чем сложность времени O (n).Интервью Q: Как найти наиболее популярное число в отсортированном массиве
Я бы сделал это с похожим подходом, как бинарный поиск.
Сначала я бы нашел значения из 8 чисел, которые были бы на 0/8, 1/8, 2/8 ... 8/8 массива. Те же самые числа, которые вы находите, когда вы бинарно ищете что-то.
Поскольку такое же число должно быть в n/4 размера массива или выше, оно должно достигать по меньшей мере двух из этих границ в строке. Аналогично номеру 2/8 и 3/8.
Поэтому идентификация номера и частичного положения выполняется в постоянное время.
Затем вы просто продолжаете находить, где оно начинается и где оно заканчивается, что является типичным бинарным поиском.
Сложность: O(log n)
Как вы пытаетесь решить проблему? –
Сначала я дал решение хэшмапа, которое требовало подсчета числа чисел и возврата числа с count> = N/4. Тогда я как бы застрял, сделав его лучше. Я знал, что популярное число (если оно существует) должно быть одним в позициях - 0, n/4, n/2, 3n/4, n, но не могло найти код для его решения. – user1952143