Линейный алгоритм большинства времени?

Ответ 1

Я бы предположил, что алгоритм Бойера-Мура (связанный с nunes и описанный cldy в других ответах) является предполагаемым ответом на вопрос; но определение "элемента большинства" в вопросе слишком слабое, чтобы гарантировать, что алгоритм будет работать.

Если n - размер списка. Элемент most - это элемент, который имеет место, по крайней мере, ceil (n/2) раз.

Алгоритм Бойера-Мура находит элемент со строгим большинством, если такой элемент существует. (Если вы не знаете заранее, что у вас есть такой элемент, вам нужно сделать второй проход через список, чтобы проверить результат.)

Для строгого большинства вам нужно "... строго больше, чем пол (n/2) раз", а не "... по крайней мере, ceil (n/2) раз".

В вашем примере "1" встречается 3 раза, а другие значения - 3 раза:

Пример ввода: 1, 2, 1, 1, 3, 2

Выход: 1

но вам нужно 4 элемента с одинаковым значением для строгого большинства.

В этом конкретном случае это работает:

Input: 1, 2, 1, 1, 3, 2
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 1: count != 0, element == candidate (1), so increment count to 2
Read 3: count != 0, element != candidate (1), so decrement count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Result is current candidate: 1

но посмотрите, что произойдет, если окончательные "1" и "2" в конце будут заменены:

Input: 1, 2, 1, 2, 3, 1
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Read 3: count == 0, so set candidate to 3, and set count to 1
Read 1: count != 0, element != candidate (3), so decrement count to 0
Result is current candidate: 3

Ответ 2

Алгоритм Бойер-Мур: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Вы просматриваете список (или поток) и поддерживаете один счетчик. Первоначально counter = 0, majority_element = null. При сканировании, если счетчик равен 0, вы принимаете текущий элемент как мажоритарный элемент и счетчик приращений. Если counter != 0, вы увеличиваете или уменьшаете счетчик в зависимости от того, является ли текущий элемент текущим элементом большинства.

Этот алгоритм не дает вам большинства, если его нет. Если вам нужен уровень правильности, вам нужно будет сделать еще один проход, чтобы проверить его на самом деле, большинство (т.е. >= 50%).

Ответ 3

Это популярный спорный вопрос, и ответ заключается в том, что это невозможно. Язык строк с элементами мажоритарности не является регулярным (это легко доказать с помощью леммы о перекачке), поэтому его невозможно распознать в константе пространство.

Конечно, фокус в том, что вам нужна переменная счетчика, которая занимает пространство O(log n), но поскольку n ограничена 2 ^ 32 или 2 ^ 64, а ваш компьютер действительно является конечным автоматом с ~ 8 ^ ( ramsize + hddsize), все O(1).

Ответ 4

Я думаю, что это возможно, используя Бойер-Мура, хотя и не напрямую.

Как сказал Матфей, ​​Бойер-Мур только гарантирует найти элемент большинства для немного другого определения большинства, называемого строгим большинством. Ваше определение немного слабее, но не намного.

• Выполнение Boyer-Moore: O (N) время, O (1) пространство
• Убедитесь, что кандидат выполняет условие: O (N) время, O (1) пробел
• Если это не так, выполните Boyer-Moore, но игнорирует экземпляры "неудавшегося" кандидата: O (N) time, O (1) space
• Убедитесь, что (новый) кандидат выполняет условие: O (N) время, O (1) пространство

1. и 2. шаги прямые. 3. работает, потому что, удаляя экземпляры несостоявшихся кандидатов, мы теперь ищем строгий элемент большинства. 4. является необязательным и используется только в том случае, если существует вероятность того, что элемент большинства отсутствует.

Ответ 5

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

Ответ 6

Я мог ошибаться, но комбинация времени выполнения O (n) и постоянного использования памяти кажется мне невозможной. Не использовать дополнительное пространство потребует сортировки. Самый быстрый выбор сравнения - O (n log n).

Используя сортировку Radix, вы можете получить лучшее время выполнения худшего случая, но больше использования памяти.

Ответ 7

Используйте предварительные стадии сортировки кучи:

• Создайте кучу для элементов массива который работает в линейном времени → O (n).

• Затем возьмите (N/2) -й элемент и выполните поиск   к верхним родительским узлам, если все   равны или нет → O (n/2)

  если все равны, то (N/2) -й элемент является ans.

так что общий O (n) + O (n/2) → O (n)