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

Question

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

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

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

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

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

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

На мой взгляд, есть две возможности

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

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

Answer 1

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

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

Answer 4

Когда контрольный пример «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;
    }

Answer 5

Я написал код 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;
}