Найти мажоритарный элемент с помощью Bit Magic

Опубликовано: 26 Февраля, 2023

Условие: элемент большинства, элемент большинства | Сет-2 (Хеширование)
Учитывая массив размера N, найдите мажоритарный элемент. Элемент большинства — это элемент, который встречается в данном массиве более n/2 раз.

Примеры:

Input: {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output: 4

Input: {3, 3, 6, 2, 4, 4, 2, 4}
Output: No Majority Element

Подход:
В этом посте мы решаем задачу с помощью двоичного представления чисел, присутствующих в массиве.
Задача состоит в том, чтобы найти элемент, который встречается более n/2 раз. Таким образом, оно оказывается больше, чем все остальные числа вместе взятые.
Итак, начиная с младшего бита (младшего бита) каждого числа массива, мы считаем, в скольких числах массива он установлен. Если какой-либо бит установлен более чем в n/2 чисел , то этот бит устанавливается в нашем мажоритарном элементе.

Приведенный выше подход работает, потому что для всех остальных объединенных чисел установленное количество битов не может быть больше n/2, так как мажоритарный элемент присутствует более n/2 раз.

Посмотрим на примере

Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Binary representation of the same are:

3 - 0 1 1
3 - 0 1 1
4 - 1 0 0
2 - 0 1 0
4 - 1 0 0
4 - 1 0 0
2 - 0 1 0
4 - 1 0 0
4 - 1 0 0
----------
  - 5 4 0

Здесь n равно 9, поэтому n/2 = 4, и только третий бит справа удовлетворяет требованию count>4 и, следовательно, устанавливается в мажоритарном элементе, а все остальные биты не устанавливаются.

Итак, наш мажоритарный элемент равен 1 0 0, что равно 4.
Но это еще не все. Этот подход работает, когда в массиве присутствует большинство элементов. А если его нет?

Давайте посмотрим с помощью этого примера:

Input : {3, 3, 6, 2, 4, 4, 2, 4}
Binary representation of the same are:

3 - 0 1 1
3 - 0 1 1
6 - 1 1 0
2 - 0 1 0
4 - 1 0 0
4 - 1 0 0
2 - 0 1 0
4 - 1 0 0
----------
  - 4 5 0

Здесь n равно 8, поэтому n/2 = 4, и только 2-й бит справа удовлетворяет count>4, и, следовательно, он должен быть установлен в мажоритарном элементе, а все остальные биты не установлены.

Таким образом, наш мажоритарный элемент в соответствии с этим равен 0 1 0, что равно 2. Но на самом деле мажоритарного элемента в массиве нет. Итак, мы делаем еще один проход по массиву, чтобы убедиться, что этот элемент присутствует более n/2 раз.

Вот реализация вышеизложенной идеи

Временная сложность: O(NlogN) , где N — количество элементов, присутствующих в массиве, время logN определяется количеством битов целого числа, а время N требуется для перебора всех элементов массива. Таким образом, временная сложность равна O(len*N), что можно записать в виде N, например O(NlogN).
Космическая сложность: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ