Требование второго прохода для алгоритма голосования большинства Бойера-Мура
Я изучаю алгоритм Бойера-Мура (из Вот) и у меня был быстрый вопрос — зачем нужен второй проход (который, по сути, просто «подтверждает», находя частоту этого элемента). Первый проход не проходит сам гарантия что найденный элемент является основным? Я рассмотрел несколько примеров и чувствовал что одного прохода достаточно. Не могли бы вы привести несколько примеров, чтобы противостоять моим чувствам?
Код (если требуется), как показано ниже:
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, Итак, действительно ли требуется второй проход? Всякий раз, когда мы кодируем, мы делаем некоторые тривиальные проверки работоспособности (например, проверяем, является ли входной вектор пустым), поэтому в этом случае, почему у нас есть «проверка работоспособности» как часть алгоритма? Или есть что-то еще?
Решение
Я думаю, что следующая интуиция для алгоритма Бойера-Мура может пролить свет на то, почему необходимы два прохода.
Алгоритм основан на следующей идее. Представьте, что каждый элемент вашего массива — это человек в комнате, держащий карточку с номером на ней. Каждый человек в комнате бродит, пока не встретит кого-то еще. Если два человека держат разные номера, каждый из них садится. В противном случае они продолжают двигаться, пока не встретят кого-то еще. В конце концов, некоторое количество людей останется стоять.
Если есть элемент истинного большинства, то группа из последних стоящих людей определенно будет иметь элемент большинства, потому что независимо от того, как люди объединяются в пары, слишком много людей в большинстве для того, чтобы их всех исключили. Но если бы не было большинства, все равно мог бы остаться кто-то, стоящий в конце с элементом, не относящимся к большинству. Например, может быть, они просто не встретили никого с другим значением, в то время как все остальные сели.
Причиной второго прохода является различие между этими двумя случаями. Если большинство вообще существует, оно должно стать окончательным кандидатом. Если этого не произойдет, что-то может все же оказаться в качестве окончательного кандидата, и вы должны исключить этот случай.
Другие решения
Я думаю, вы не понимаете, что такое элемент большинства. Кандидат квалифицируется только в том случае, если его частота превышает половину общего списка, т.е.
if frequency(majority_element) > total_size_of_list / 2: return True
Первый проход получает только возможного кандидата на голосование большинства. Второй проход подтверждает, действительно ли это элемент большинства или нет.
Например:-
В следующем списке
[1, 2, 2, 3, 3, 4, 4, 5, 5, 5]
Возможный кандидат на мажоритарный элемент — 5.
Но частота 5 в списке — это только 3, что меньше половины размера списка, и поэтому оно не является элементом большинства, поэтому тест не пройден, но вы даже не узнаете об этом, если не сделаете второй проход.
Я надеюсь, что это помогает!