Требование второго прохода для алгоритма голосования большинства Бойера-Мура

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

Код (если требуется), как показано ниже:

int majorityElement(vector<int>& nums) {
    int candidate=0, count=0;

    for(auto value: nums) {
        //update the candidate if the count == 0
        if(count==0)
            candidate=value;

        //if the value == candidate then increment count
        if(value==candidate)
            count++;
        else
        //decrement count
            count--;
    }

    //return candidate
    return candidate;
}

Изменить: Если я правильно понимаю, алгоритм применим только тогда, когда частота большинства элемента действительно больше, чем (vector size())/2, Итак, действительно ли требуется второй проход? Всякий раз, когда мы кодируем, мы делаем некоторые тривиальные проверки работоспособности (например, проверяем, является ли входной вектор пустым), поэтому в этом случае, почему у нас есть "проверка работоспособности" как часть алгоритма? Или есть что-то еще?

Источник

3 ответа

Решение

Я думаю, что следующая интуиция для алгоритма Бойера-Мура может пролить свет на то, почему необходимы два прохода.

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

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

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

Источник

Я думаю, вы не понимаете, что такое элемент большинства. Кандидат квалифицируется только в том случае, если его частота превышает половину всего списка, т.е.

if frequency(majority_element) > total_size_of_list / 2: return True

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

Например:- В следующем списке

[1, 2, 2, 3, 3, 4, 4, 5, 5, 5]

Возможный кандидат на мажоритарный элемент - 5. Но частота 5 в списке - только 3, что меньше половины размера списка, и, следовательно, это не элемент мажоритарности, поэтому тест не пройден, но вы даже не узнаете его, если не наденете. не делайте второй проход.

Я надеюсь, что это помогает!

Источник

Я думаю, что второй проход требуется, когда вам нужно сравнить свой элемент с верхним пределом, если вы хотите найти только элемент, который повторяется более чем n/2, чем первый проход сделает работу

Источник
Другие вопросы по тегам