21.09.2022 18:40
Andrey210 12 3000 Источник

Введение

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

Комментарии (12)


  1. Biga
    21.09.2022 22:15
    #24756540

    Сразу приходят на ум распределённые базы данных с правилом успешной записи в N/2+1 реплику. Применяют там такой алгоритм?


  1. AndreyDmitriev
    21.09.2022 22:30
    #24756576
    +1

    Если допустить, что кандидаты нумеруются с единицы и последовательно (либо нам заранее известен максимальный номер ну или если у нас есть неограниченное количество памяти), то можно в общем и в один проход, используя гистограмму, ну вот как-то так что ли:

      public static int findMajority(int[] nums)
  {
    int count = 0, candidate = -1;
    int[] histo = new int[nums.Length + 1]; //Assumed sequential order
     // Finding majority candidate
    for (int index = 0; index < nums.Length; index++) {
      if (histo[nums[index]]++ > count) {
         count = histo[nums[index]];
         candidate = nums[index];
      }
    }
    if (count > (nums.Length / 2)) return candidate; else return -1;
  }


    1. domix32
      22.09.2022 00:51
      #24757000
      +2

      Тут пространственная сложность становится O(N) на выделение собственно гисты. Теоретически можно пожать исходный массив при помощи RLE, но тут все равно крайние случаи возникают.


      1. AndreyDmitriev
        22.09.2022 07:31
        #24757186

        Да, согласен. Я просто очень похожий метод в одном проекте использовал. Идея комбинации c RLE весьма любопытна, спасибо.


    1. sunnybear
      22.09.2022 08:28
      #24757250
      +1

      Сортировка имеет сложность больше чем O(1)


  1. Andriljo
    21.09.2022 23:54
    #24756820

    Теория принятия решений подъехала, любо.


  1. Alexandroppolus
    22.09.2022 03:14
    #24757096
    +3

    Классика )

    Прикольно, что этот подход можно обобщить на поиск (k-1) элементов, каждый из которых встречается более 1/k раз. Например, если k=3, то вместо аннигиляции пар элементов аннигилируем тройки.


  1. kchhay
    23.09.2022 12:23
    #24760452

    Еще есть алгоритм, не шибко расширяемый в общем случае, но все равно забавный. Если говорить о числах, можем каждое встреченное число разбивать на биты и суммировать вхождения каждого бита.
    В конце за О(log(максимальное число)) проходим по массиву битов и берем только те, которые встречаются больше половины раз.
    Очевидно, это не сработает, если нам не гарантировано, что такое число вообще есть (а если гарантированно - то и Бойер-Мур сработает за одну линию). Контртест - банальный
    (1,2,3). При подсчете битов получим (0,2,2) - что даст неправильный ответ 3.

    Но, подозреваю, что по времени работы эти алгоритмы вполне соизмеримы на больших массивах.


    1. Andrey210 Автор
      23.09.2022 12:30
      #24760492

      Класно! Очень необычный подход. В таком формате над этой задачей я не думал даже. Не очень понял, почему O(log(n)) для прохождения по массиву битов, но если инты брать, то можно за константу по битам пройтись. Проблема будет наверное только со знаковым битом.


      1. kchhay
        23.09.2022 16:09
        #24761598

        Там, все же, не O(log(n)), а O(log(максимальное число)), потому что в общем случае никто не гарантирует, что числа на входе помещаются в int. Если максимальное число включает в себя 10000 бит - то и этот массив с битами будет 10000 и по нему тоже придется пройтись.
        По поводу идеи с интом, можно:
        1) Если мы знаем размер массива заранее.
        2) Если мы знаем, что существует такой элемент.
        3) Если мы знаем битность максимально-возможного числа.
        Тогда в ответ вписывать бит как только кол-во его вхождений перевалит за половину. Тогда этот последний обход можно упразднить.

        Но, конечно, исходный алгоритм намного проще расширять. Скажем, если там не числа, а строки, или вообще какие-то кастомные классы. Можно, конечно, что-то с хешами выдумывать, конвертировать в void*, писать свои превращения класса в bitfield - но Бойер-Мур явно и понятно, без всяких извращений - работает для любых типов, для которых определены operator= и operator==.
        И все равно алгоритм с битами - прикольный.


    1. Alexandroppolus
      23.09.2022 16:07
      #24761592

      Тут придется на каждой итерации проходить биты числа. Асимптотика линейная, а работать будет дольше.

      Ну и можно такое делать не только на целых, а и на вещественных числах. В некоторых языках (напр., с, с++, js) есть возможность смотреть биты вещественных чисел.


      1. kchhay
        23.09.2022 17:43
        #24761858

        А что, по-вашему, сравнение двух чисел происходит как-то не по-битово? Конечно, компилятор это делает как-то быстрее, сравнивая не по одному биту, а по 32, скажем, или по 64. Собственно, поэтому мы и опускаем этот множитель из асимптотики в алгоритме Бойера-Мура, хотя там есть и сравнения, и присваивания.
        Я сразу указал, что асимптотика будет не просто O(n), а, O(n * log(max(num))). Что можно ограничить сверху константой. Иногда. Ну, например 64.
        O(64n)=O(n). Для больших массивов чисел эта константа роли не играет, сильно зависит от реализации и все такое.
        Для желающих поиграться с оптимизацией, вот запилил на quickbench: https://quick-bench.com/q/AB50Bom9Nn1x9ZXkpTGKGEr_njQ
        И, ожидаемо, Бойера-Мура быстрее. В зависимости от данных - вплоть до двух порядков быстрее.