Алгоритм большинства голосов Бойера — Мура

Введение

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