Нахождение сильно преобладающего элемента последовательности >n/2 (алгоритм большинства голосов Бойера-Мура)

[wataru]

У вас задачи перепутаны.

Кратко: на вход мы получаем массив, состоящий из чисел. Нужно найти число, которое встречается наибольшее количество раз. 

Не супер очевидно, но это число занимает больше половины элементов массива, т.е.

Не очевидно, потому что это ни откуда не следует. В указанной вами задаче https://leetcode.com/problems/most-frequent-even-element/description/ такого перобладающего элемента вообще нет. Есть другая задача, где условие про "больше половины" задано в задаче: https://leetcode.com/problems/majority-element/description/

[akozyrenko]

В ссылке, действительно, была ошибка. Скорректировала.

[wataru]

Тогда можно убрать условие про "встречается больше всех раз". В задаче этого условия нет. Потому что если элемент встречается больше половины раз, то он точно встречается больше всех остальных (даже вместе взятых, а уж по отдельности точно).

[akozyrenko]

Согласна, скорректировала.

[wataru]

И еще, вы бы хоть показали, почему этот алгоритм вообще работает.

[sci_nov]

Получается, алгоритм находит моду дискретной случайной величины?

[wataru]

Только если она сильно доминирует - встречается хотябы половину раз во входном потоке. Ну и вообще, если величина случайная, то мода с ненулевой вероятностью может выпасть меньшее количество раз чем соседнее значение.

[sci_nov]

А что значит соседнее значение?

[wataru]

Ну, если гистограмма "хорошая", то соседние значения имеют почти такую-же высокую вероятность выпадения, каки мода. Но чуть поменьше. Но в общем случае, там не соседнее значение будет идти вторым по вероятности и можно получить случайно его.

[sci_nov]

А, понял, то есть данный алгоритм намного более простой, чем алгоритм нахождения моды, потому что мод может быть несколько.

[wataru]

Нет, он проще потому что тут не просто "мода", а сильно переобладающий элемент - он должен встречатся строго более половины раз.

[sci_nov]

Да, ПЭ - мода, но не всякая мода - ПЭ)

[DmitryZlobec]

if (count == 0) { candidate = nums[i]; }

Я бы сохранил индекс в массиве где лежит элемент.

[homesoft]

Для последовательности 1,2,3,1,4,5,1,6,7,1,8,9 должно находить 1 ?

[akozyrenko]

Нет, задача алгоритма (и, собственно, условие самой задачи на leetcode) найти число, которое встречается больше, чем n/2 раз, где n - длина входного массива.

[homesoft]

Просто в статье сначала идёт речь о "преобладающем элементе" (который будет в случае моего примера 1), потом о "преобладающем элементе, встречающемся более n/2 раз". Это может вводить в заблуждение..

[akozyrenko]

Скорректировала:) надеюсь, теперь не будет путаницы

Ну, и, кстати в статье уже был пример, похожий на ваш, где я написала, что в таком случае нет преобладающего элемента.

[Alexandroppolus]

Почему вообще работает алгоритм и почему такой элемент всего один? Если бы существовали два различных элемента, которые каждый встречался бы более чем ⌊n/2⌋ раз, то их суммарное количество появлений превысило бы n, что невозможно.

На самом деле алгоритм обобщается на k элементов, каждый из которых встречается более чем ⌊n/(k+1)⌋ раз. Но это k надо знать заранее и сделать k счетчиков. Далее, смотрим очередной v = a[i]. Если этот v равен элементу на одном из занятых счетчиков, то увеличиваем данный счетчик, иначе если есть пустой счетчик, v его занимает, иначе все k счетчиков уменьшаются на 1. По итогу на счетчиках останутся искомые числа.

[HubForCyc1e]

Было бы здорово посмотреть видео объяснение, для новичков так легче приходит понимание, а за статьи отдельное спасибо!))

[akozyrenko]

Спасибо:) над видео подумаю🙂