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

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

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

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

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

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

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

Как я вижу, есть две возможности

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

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

Ответы

Ответ 1

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

Ответ 2

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

  • первая часть запуска алгоритма Moore Voting дает только кандидату для элемента большинства. Обратите внимание на слово "кандидат".

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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;
}

Ответ 5

Когда тестовый пример "AAACCBB", набор не имеет большинства. Поскольку ни один элемент не встречается более трех раз, так как длина "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;
    }