Алгоритм голосования с линейным временем. я не понимаю

Когда я читал это (Найдите наиболее распространенную запись в массиве), линейное время Бойера и Мура Был предложен алгоритм голосования.

Если пройти по ссылке на сайт, там есть пошаговое объяснение того, как работает алгоритм. Для данной последовательности AAACCBBCCCBCC это верное решение.

Когда мы перемещаем указатель вперед над элементом e:

  • Если счетчик равен 0, мы устанавливаем для текущего кандидата значение e, а для счетчика устанавливаем значение 1.
  • Если счетчик не равен 0, мы увеличиваем или уменьшаем значение счетчика в зависимости от того, является ли e текущим кандидатом.

Когда мы закончим, текущий кандидат будет элементом большинства, если есть большинство.

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

Как я понимаю, есть два варианта

  1. Авторы никогда не пробовали свой алгоритм ни на чем другом, кроме AAACCBBCCCBCC, они совершенно некомпетентны и должны быть немедленно уволены (сомнительно).
  2. Я явно что-то упускаю, должен быть забанен в Stackoverflow и мне никогда больше не разрешат прикасаться к чему-либо, связанному с логикой.

Примечание. Вот реализация алгоритма на C++ от Niek Sanders. . Я считаю, что он правильно реализовал идею, и поэтому у него такая же проблема (или нет?).


algorithm puzzle language-agnostic
person Lieven Keersmaekers    schedule 23.04.2009    source источник

Ответы (5)


arrow_upward
45
arrow_downward

Алгоритм работает только тогда, когда набор имеет большинство — более половины элементов одинаковы. AAACCBB в вашем примере такого большинства нет. Наиболее часто встречающаяся буква встречается 3 раза, длина строки 7.

person Rafał Dowgird    schedule 23.04.2009
comment
Бывает со всеми. Не будьте слишком строги в выполнении пункта 2. из вашего ответа :) - person Rafał Dowgird; 23.04.2009
comment
хорошо, теперь я вижу это. Алгоритм утверждает, что этот алгоритм решает, какой элемент последовательности составляет большинство. На первый взгляд пропустил большую часть и предположил, что речь идет о том, что элемент появляется максимальное количество раз. Большинство здесь означает, что элемент должен появляться как минимум в два раза меньше элементов! - person texens; 04.09.2013
comment
Вы имеете в виду больше половины, а не минимум половины. - person Hiroki Osame; 27.01.2014

arrow_upward
28
arrow_downward

Небольшое, но важное дополнение к другим объяснениям. Алгоритм голосования Мура состоит из 2 частей:

  1. первая часть алгоритма голосования Мура дает вам кандидата для элемента большинства. Обратите внимание на слово «кандидат».

  2. Во второй части нам нужно пройтись по массиву еще раз, чтобы определить, встречается ли этот кандидат максимальное количество раз (т. е. больше, чем size/2 раза).

Первая итерация — найти кандидата, а вторая — проверить, встречается ли этот элемент большинство раз в данном массиве.

Итак, временная сложность: O(n) + O(n) ≈ O(n)

person Srikar Appalaraju    schedule 03.07.2013
comment
+1 Я собирался написать о совершенно упущенном из виду факте, что для проверки кандидата необходима вторая итерация. Надеюсь, ОП заметит этот поздний ответ. - person imreal; 23.07.2013
comment
Объяснение от самого автора: cs.utexas.edu/ пользователи/moore/best-ideas/mjrty/index.html - person Anupam Saini; 29.12.2014
comment
Шаг 1 не дает вам самого частого кандидата. AAABBCC даст вам C как окончательный кандидат, но C не является наиболее частым или большинством. Затем вы запускаете второй проход, чтобы увидеть, что этот массив не имеет большинства. - person lineil; 01.02.2016

arrow_upward
7
arrow_downward

Из первого связанного вопроса SO:

со свойством, что более половины элементов массива равны N

Со страницы Бойера и Мура:

какой элемент последовательности составляет большинство при условии, что такой элемент существует

Оба этих алгоритма явно предполагают, что один элемент встречается не менее N/2 раз. (Обратите внимание, в частности, что «большинство» — это не то же самое, что «наиболее распространенный».)

person j_random_hacker    schedule 23.04.2009
comment
+1. Закрыть второй. Не могу поверить, что я проглядел это. Спасибо. - person Lieven Keersmaekers; 23.04.2009

arrow_upward
0
arrow_downward

Я написал код C++ для этого алгоритма

char find_more_than_half_shown_number(char* arr, int len){
int i=0;
std::vector<int> vec;
while(i<len){
    if(vec.empty()){     
        vec.push_back(arr[i]);
        vec.push_back(1);
    }else if(vec[0]==arr[i]){ 
        vec[1]++;
    }else if(vec[0]!=arr[i]&&vec[1]!=0){
        vec[1]--;
    }else{                   
        vec[0]=arr[i];
    }
    i++;
}
int tmp_count=0;
for(int i=0;i<len;i++){
    if(arr[i]==vec[0])
        tmp_count++;
}
if(tmp_count>=(len+1)/2)
    return vec[0];
else
    return -1;
}

и основная функция, как показано ниже:

int main(int argc, const char * argv[])
{
    char arr[]={'A','A','A','C','C','B','B','C','C','C','B','C','C'};
    int len=sizeof(arr)/sizeof(char);
    char rest_num=find_more_than_half_shown_number(arr,len);
    std::cout << "rest_num="<<rest_num<<std::endl;
    return 0;
}
person feliciafay    schedule 29.01.2014

arrow_upward
0
arrow_downward

Когда контрольный пример "AAACCBB", набор не имеет большинства. Поскольку ни один элемент не встречается более 3 раз, поскольку длина «AAACCBB» равна 7.

Вот код для «Алгоритма голосования по линейному времени Бойера и Мура»:

int Voting(vector<int> &num) {
        int count = 0;
        int candidate;

        for(int i = 0; i < num.size(); ++i) {
            if(count == 0) {
                candidate = num[i];
                count = 1;
            }
            else
                count = (candidate == num[i]) ? ++count : --count;
        }
        return candidate;
    }
person Peter Rui    schedule 23.12.2014