Введение
Решал задачки на LeetCode и вот небольшой переводик небольшой статьи про небольшой алгоритм.
Алгоритм голосования Бойера-Мура является одним из самых популярных и оптимальных алгоритмов, который используется для поиска преобладающего элемента среди заданных, который имеет более N / 2 вхождений. Алгоритм выполняет 2 обхода по заданным элементам, что работает при O (N) временной сложности и O (1) пространственной сложности.
Input :{1,1,1,1,2,3,5}
Output : 1
Input : {1,2,3}
Output : -1
Если какой-то элемент встречается больше N/2 раз то отличных от него элементов меньше N/2. Собственно алгоритм на этом и держится.
Для начала выбирается элемент кандидат. Далее для каждого элемента:
- если элемент равен кандидату, количество голосов увеличивается.
- если кандидат и элемент не равны, количество голосов уменьшается.
- если голосов 0, выбирается новый кандидат.
На словах
По сути, увеличивая или уменьшая количество голосов мы увеличиваем или уменьшаем приоритет определенного кандидата. Это сработает, поскольку правильный кандидат встретится более N/2 раз. Если количество голосов оказалось 0, это означает, что элементов отличных от кандидата, столько-же, сколько и равных ему. Получается текущий кандидат не может быть большинством и мы выбираем следующего кандидата. Окончательный кандидат и будет преобладающим элементом, если такой присутствует. Вторым проходом проверим, что полученный элемент встречается больше N / 2 раз. Если нет то такого элемента нет.
От слов к коду
public static Integer findMajority(int[] nums)
{
int count = 0;
Integer candidate = null;
for (int num : nums) {
// проверяем, если количество голосов 0 меняем кандидата
if (count == 0) {
candidate = num;
}
// если кандидат и число совпали увеличиваем кол-во голосов
// иначе уменьшаем
count += (num == candidate) ? 1 : -1;
}
count = 0;
// считаем количество элементов равных кандидату
// в исходном массиве
for (int num : nums) {
if (num == candidate)
count++;
}
// если кандидат подходит условию возвращаем его
// иначе возвращаем null;
if (count > (nums.length / 2)) return candidate;
else return null;
}
Top comments (0)