Алгоритм большинства голосов 뵈예라 - 무라

베데니에



Решал задачки на LeetCode 와 вот небольшой переводик небольшой статьи про небольшой 알고리즘.
Алгоритм голосования Бойера-Мура является одним из самых популярных и оптимальных алгоритмов, который используется для поиска преобладающего элемента среди заданных, который имеет более N/2 вхождений. Алгоритм выполняет 2 обхода по заданным элементам, что работает при O (N) вреmenнной сложности и 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, это означает, что элементов отличных от кандидата, столько-же, сколько и равных ему. Получается текущий кандидат не может быть большинством и мы выбираем следующего кандидата. окончательный кандидат и будет преобладающим элементом, если такой присутствует. Вторым проходом проверим, что полученный элеmentент встречается больше 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;
      }
    

    좋은 웹페이지 즐겨찾기