Requisito previo: elemento mayoritario , elemento mayoritario | Conjunto-2 (Hashing)
Dada una array de tamaño N, encuentre el elemento mayoritario. El elemento mayoritario es el elemento que aparece más de n/2 veces en el arreglo dado.
Ejemplos:
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
Enfoque:
en esta publicación, resolvemos el problema con la ayuda de la representación binaria de los números presentes en la array.
La tarea es encontrar el elemento que aparece más de n/2 veces. Por lo tanto, aparece más que todos los demás números combinados.
Entonces, comenzando desde LSB (bit menos significativo) de cada número de la array, contamos en cuántos números de la array se establece. Si algún bit se establece en más de n/2 números , entonces ese bit se establece en nuestro elemento mayoritario.
El enfoque anterior funciona porque para todos los demás números combinados, el número de bits establecido no puede ser mayor que n/2, ya que el elemento mayoritario está presente más de n/2 veces.
Veamos con la ayuda del ejemplo.
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
Aquí n es 9, por lo que n/2 = 4 y un solo tercer bit desde la derecha satisface la cuenta> 4 y, por lo tanto, se establece en el elemento mayoritario y todos los demás bits no se establecen.
Por lo tanto, nuestro elemento mayoritario es 1 0 0, que es 4
Pero hay más, este enfoque funciona cuando el elemento mayoritario está presente en la array. ¿Qué pasa si no está presente?
Veamos con la ayuda de este ejemplo:
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
Aquí n es 8, por lo que n/2 = 4 y un solo segundo bit desde la derecha satisface la cuenta> 4 y, por lo tanto, debe establecerse en el elemento mayoritario y todos los demás bits no deben establecerse.
Entonces, nuestro elemento mayoritario de acuerdo con esto es 0 1 0, que es 2 Pero en realidad el elemento mayoritario no está presente en la array. Entonces, hacemos una pasada más de la array, para asegurarnos de que este elemento esté presente más de n/2 veces.
Aquí está la implementación de la idea anterior.
C++
#include <iostream>
using namespace std;
void findMajority(int arr[], int n)
{
// Number of bits in the integer
int len = sizeof(int) * 8;
// Variable to calculate majority element
int number = 0;
// Loop to iterate through all the bits of number
for (int i = 0; i < len; i++) {
int count = 0;
// Loop to iterate through all elements in array
// to count the total set bit
// at position i from right
for (int j = 0; j < n; j++) {
if (arr[j] & (1 << i))
count++;
}
// If the total set bits exceeds n/2,
// this bit should be present in majority Element.
if (count > (n / 2))
number += (1 << i);
}
int count = 0;
// iterate through array get
// the count of candidate majority element
for (int i = 0; i < n; i++)
if (arr[i] == number)
count++;
// Verify if the count exceeds n/2
if (count > (n / 2))
cout << number;
else
cout << "Majority Element Not Present";
}
// Driver Program
int main()
{
int arr[] = { 3, 3, 4, 2, 4, 4, 2, 4, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
findMajority(arr, n);
return 0;
}
Java
class GFG
{
static void findMajority(int arr[], int n)
{
// Number of bits in the integer
int len = 32;
// Variable to calculate majority element
int number = 0;
// Loop to iterate through all the bits of number
for (int i = 0; i < len; i++)
{
int count = 0;
// Loop to iterate through all elements in array
// to count the total set bit
// at position i from right
for (int j = 0; j < n; j++)
{
if ((arr[j] & (1 << i)) != 0)
count++;
}
// If the total set bits exceeds n/2,
// this bit should be present in majority Element.
if (count > (n / 2))
number += (1 << i);
}
int count = 0;
// iterate through array get
// the count of candidate majority element
for (int i = 0; i < n; i++)
if (arr[i] == number)
count++;
// Verify if the count exceeds n/2
if (count > (n / 2))
System.out.println(number);
else
System.out.println("Majority Element Not Present");
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 3, 3, 4, 2, 4, 4, 2, 4, 4 };
int n = arr.length;
findMajority(arr, n);
}
}
// This code is contributed by AnkitRai01
Python3
def findMajority(arr, n):
# Number of bits in the integer
Len = 32
# Variable to calculate majority element
number = 0
# Loop to iterate through
# all the bits of number
for i in range(Len):
count = 0
# Loop to iterate through all elements
# in array to count the total set bit
# at position i from right
for j in range(n):
if (arr[j] & (1 << i)):
count += 1
# If the total set bits exceeds n/2,
# this bit should be present in
# majority Element.
if (count > (n // 2)):
number += (1 << i)
count = 0
# iterate through array get
# the count of candidate majority element
for i in range(n):
if (arr[i] == number):
count += 1
# Verify if the count exceeds n/2
if (count > (n // 2)):
print(number)
else:
print("Majority Element Not Present")
# Driver Code
arr = [3, 3, 4, 2, 4, 4, 2, 4, 4]
n = len(arr)
findMajority(arr, n)
# This code is contributed by Mohit Kumar
C#
using System;
class GFG
{
static void findMajority(int []arr, int n)
{
// Number of bits in the integer
int len = 32;
// Variable to calculate majority element
int number = 0;
// Loop to iterate through all the bits of number
for (int i = 0; i < len; i++)
{
int count = 0;
// Loop to iterate through all elements
// in array to count the total set bit
// at position i from right
for (int j = 0; j < n; j++)
{
if ((arr[j] & (1 << i)) != 0)
count++;
}
// If the total set bits exceeds n/2,
// this bit should be present in majority Element.
if (countt > (n / 2))
number += (1 << i);
}
int count = 0;
// iterate through array get
// the count of candidate majority element
for (int i = 0; i < n; i++)
if (arr[i] == number)
count++;
// Verify if the count exceeds n/2
if (count > (n / 2))
Console.Write(number);
else
Console.Write("Majority Element Not Present");
}
// Driver Code
static public void Main ()
{
int []arr = { 3, 3, 4, 2, 4, 4, 2, 4, 4 };
int n = arr.Length;
findMajority(arr, n);
}
}
// This code is contributed by @Tushi..
Javascript
<script>
function findMajority(arr, n)
{
// Number of bits in the integer
let len = 32;
// Variable to calculate majority element
let number = 0;
// Loop to iterate through all
// the bits of number
for(let i = 0; i < len; i++)
{
let countt = 0;
// Loop to iterate through all elements
// in array to count the total set bit
// at position i from right
for(let j = 0; j < n; j++)
{
if ((arr[j] & (1 << i)) != 0)
countt++;
}
// If the total set bits exceeds n/2,
// this bit should be present in
// majority Element.
if (countt > parseInt(n / 2, 10))
number += (1 << i);
}
let count = 0;
// Iterate through array get
// the count of candidate
// majority element
for(let i = 0; i < n; i++)
if (arr[i] == number)
count++;
// Verify if the count exceeds n/2
if (count > parseInt(n / 2, 10))
document.write(number);
else
document.write("Majority Element Not Present");
}
// Driver Code
let arr = [ 3, 3, 4, 2, 4, 4, 2, 4, 4 ];
let n = arr.length;
findMajority(arr, n);
// This code is contributed by decode2207
</script>
4
Complejidad del tiempo: O(NlogN) Donde N es el número de elementos presentes en el arreglo, el tiempo logN es tomado por el número de bits de un número entero y N tiempo es tomado para iterar todos los elementos del arreglo. Entonces, la complejidad del tiempo es O (len * N), que se puede escribir en forma de N como este O (NlogN).
Complejidad espacial: O(1)
Publicación traducida automáticamente
Artículo escrito por Ankur Goel y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA