[Перевод] Алгоритм большинства голосов Бойера — Мура21.09.2022 20:02

11c247b668d6ae374932f495467533c6.png

#Введение#
Решал задачки на 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;
  }

© Habrahabr.ru