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

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

Если n-размер списка, то мажоритарный элемент - это элемент, который встречается не менее {2]} раз.

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

[Output] 1

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

7 13
language-agnostic algorithm complexity-theory

7 ответов:

Я бы предположил, что алгоритм Бойера-Мура (связанный с 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
14

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

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

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

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

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

7

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

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

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

7

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

2

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

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

0

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

  1. Постройте кучу для элементов массива который работает в линейном времени - > O (n).

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

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

Таким образом, в целом O (n) + O (n / 2) - > O (n)

0