Comments 20
У вас задачи перепутаны.
Кратко: на вход мы получаем массив, состоящий из чисел. Нужно найти число, которое встречается наибольшее количество раз.
Не супер очевидно, но это число занимает больше половины элементов массива, т.е.
Не очевидно, потому что это ни откуда не следует. В указанной вами задаче https://leetcode.com/problems/most-frequent-even-element/description/ такого перобладающего элемента вообще нет. Есть другая задача, где условие про "больше половины" задано в задаче: https://leetcode.com/problems/majority-element/description/
В ссылке, действительно, была ошибка. Скорректировала.
И еще, вы бы хоть показали, почему этот алгоритм вообще работает.
Получается, алгоритм находит моду дискретной случайной величины?
Только если она сильно доминирует - встречается хотябы половину раз во входном потоке. Ну и вообще, если величина случайная, то мода с ненулевой вероятностью может выпасть меньшее количество раз чем соседнее значение.
А что значит соседнее значение?
Ну, если гистограмма "хорошая", то соседние значения имеют почти такую-же высокую вероятность выпадения, каки мода. Но чуть поменьше. Но в общем случае, там не соседнее значение будет идти вторым по вероятности и можно получить случайно его.
if (count == 0) { candidate = nums[i]; }
Я бы сохранил индекс в массиве где лежит элемент.
Для последовательности 1,2,3,1,4,5,1,6,7,1,8,9 должно находить 1 ?
Нет, задача алгоритма (и, собственно, условие самой задачи на leetcode) найти число, которое встречается больше, чем n/2 раз, где n - длина входного массива.
Просто в статье сначала идёт речь о "преобладающем элементе" (который будет в случае моего примера 1), потом о "преобладающем элементе, встречающемся более n/2 раз". Это может вводить в заблуждение..
Почему вообще работает алгоритм и почему такой элемент всего один? Если бы существовали два различных элемента, которые каждый встречался бы более чем ⌊n/2⌋ раз, то их суммарное количество появлений превысило бы n, что невозможно.
На самом деле алгоритм обобщается на k элементов, каждый из которых встречается более чем ⌊n/(k+1)⌋ раз. Но это k надо знать заранее и сделать k счетчиков. Далее, смотрим очередной v = a[i]. Если этот v равен элементу на одном из занятых счетчиков, то увеличиваем данный счетчик, иначе если есть пустой счетчик, v его занимает, иначе все k счетчиков уменьшаются на 1. По итогу на счетчиках останутся искомые числа.
Было бы здорово посмотреть видео объяснение, для новичков так легче приходит понимание, а за статьи отдельное спасибо!))
Нахождение сильно преобладающего элемента последовательности >n/2 (алгоритм большинства голосов Бойера-Мура)