Нахождение преобладающего элемента последовательности (алгоритм большинства голосов Бойера-Мура)

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

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

Предлагаю сразу использовать его на примере задачи «Majority Element» с leetcode.

Условие здесь: https://leetcode.com/problems/majority-element/description/

Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)

Возвращаемся к Муру!

Кратко: на вход мы получаем массив, состоящий из чисел. Нужно найти число, которое встречается наибольшее количество раз и занимает больше половины элементов массива (n/2), т.е.

• [1,1,2] - преобладающий элемент 1

• [3,10,56,3] - преобладающего элемента нет

• [3,10,35,3,3] - преобладающий элемент 3

Ограничения c leetcode: 

• Длина массива от 1 до 5 * 10^4

• Значения массива от -10^9 до 10^9

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

Код на Java выглядел бы так:

public int majorityElement(int[] nums) {

  Map<Integer, Integer> majorMap = new HashMap(); 

  for (int i = 0; i < nums.length; i++) {

      majorMap.put(nums[i], majorMap.getOrDefault(nums[i], 0) + 1); 

  }

   int majorElement = 0;

   int maxMajority = 0;

   for (Map.Entry<Integer, Integer> entry: majorMap.entrySet()) {

      int currElement = entry.getKey();

      int majority = entry.getValue();

      if (majority > maxMajority) {

         maxMajority = majority;

         majorElement = currElement;

      }

   }

   return majorElement;

}

Временная сложность такого алгоритма составит О(n), поскольку мы один раз проходимся по массиву - O(n) и один раз по хэш-таблице O(m), т.е. Общая сложность O(n+m)~ O(n)

Пространственная сложность: O(n), так как количество элементов в хэш-таблицы будет зависеть от размера входного массива.

Что позволяет сделать алгоритм Бойера-Мура в данном случае?

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

Итак, сам алгоритм.

Проходим по каждому элементу заданной последовательности, проверяем значение счетчика. Если счетчик равен 0, то текущий элемент становится потенциальным кандидатом на преобладающий элемент (далее candidate), а счетчик увеличивается на 1. Далее если candidate равен текущему элементу, счетчик увеличивается, а если нет, то уменьшается.

Если мы не уверены, что в последовательности существует такой элемент, то нужно пройти по ней еще раз и убедится, что элемент встречается в массиве более чем n/2, где n - длина массива. P.S. В задаче с leetcode это не нужно, т.к. нам гарантируют, что такой элемент точно есть.

Почему вообще работает алгоритм и почему такой элемент всего один? Если бы существовали два различных элемента, которые каждый встречался бы более чем ⌊n/2⌋ раз, то их суммарное количество появлений превысило бы n, что невозможно.

Итак код:

public static int majorityElement(int[] nums) {
  //Часть 1 - Находим «кандидата на большинство»
  int candidate = nums[0];
  int count = 1;

  for (int i = 1; i < nums.length; i++) {
      if (count == 0) {
          candidate = nums[i];
      }
      count += (nums[i] == candidate) ? 1 : -1;
  }

  //Часть №2 - Проверяем, является ли кандидат большинством
  //не нужна для leetcode
  count = 0;
  for (int num : nums) {
      if (num == candidate) {
          count++;
      }
  }

  if (count > nums.length / 2) {
      return candidate;
  } else {
      throw new IllegalArgumentException("No majority element found");
  }
}

Вывод: алгоритм позволяет сократить пространственную сложность до О(1), что полезно, надо сказать:)