Найти мажоритарный элемент с помощью Bit Magic
Условие: элемент большинства, элемент большинства | Сет-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)