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

Question

Может кто-нибудь придумать алгоритм линейного времени для определения элемента большинства в списке элементов? Алгоритм должен использовать O(1) пробел.

Если n - размер списка, элемент большинства - это элемент, который встречается не менее ceil(n / 2) раз.

[Input] 1, 2, 1, 1, 3, 2

[Output] 1

[Заметка редактора] Этот вопрос имеет техническую ошибку. Я предпочел оставить это, чтобы не испортить формулировку принятого ответа, который исправляет ошибку и обсуждает почему. Пожалуйста, проверьте принятый ответ.

Answer 1

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

Если n - размер списка.Мажоритарный элемент - это элемент, который встречается как минимум в 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

Answer 2

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

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

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

Answer 3

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

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

1. Выполнить Бойера-Мура: O (N) время, O (1) пробел
2. Убедитесь, что кандидат удовлетворяет условию: O (N) время, O (1) пробел
3. Если этого не произойдет, выполнить Бойер-Мур, но игнорирует случаи «провал» кандидата: O (N) время, O (1) пробел
4. Убедитесь, что (новый) кандидат удовлетворяет условию: O (N) время, O (1) пробел

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

Answer 4

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

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

Answer 5

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

Answer 6

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

1. Создание кучи для элементов массива, работающих за линейное время -> O (n).

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

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

, поэтому в целом O (n) + O (n / 2) -> O (n)

Answer 7

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

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