Dada una array arr[] que consiste en N enteros, la tarea es encontrar todos los elementos de la array que ocurren más de un piso (n/3) veces.
Ejemplos:
Entrada: arr[] = {5, 3, 5}
Salida: 5
Explicación:
La frecuencia de 5 es 2, que es mayor que N/3 (3/3 = 1).Entrada: arr[] = {7, 7, 7, 3, 4, 4, 4, 5}
Salida: 4 7
Explicación:
La frecuencia de 7 y 4 en el arreglo es 3, que es más que N/3( 8 /3 = 2).
Método 1:
Enfoque: la solución básica es tener dos bucles y realizar un seguimiento del recuento máximo de todos los elementos diferentes. Si el recuento máximo es mayor que n/3, imprímalo. Si el conteo máximo no supera los n/3 después del recorrido de la array, entonces el elemento mayoritario no existe.
C++
// C++ program to find Majority
// element in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find Majority element
// in an array
void findMajority(int arr[], int n) {
int flag = 0;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = i; j < n; j++) {
if (arr[i] == arr[j]) {
count++;
}
}
if (count > (n / 3)) {
cout << arr[i] << " ";
flag = 1;
}
}
if (!flag)
cout << "No Majority Element" << endl;
}
int main() {
int arr[] = { 2, 2, 3, 1, 3, 2, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function calling
findMajority(arr, n);
return 0;
}
// This code is contributed by Aman Chowdhury
Java
// Java program to find Majority
// element in an array
import java.io.*;
class GFG {
// Function to find Majority element
// in an array
static void findMajority(int arr[], int n)
{
int flag=0;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = i; j < n; j++) {
if (arr[i] == arr[j])
count++;
}
// if count is greater than n/3 means
// current element is majority element
if (count > n/3) {
System.out.print(arr[i]+" ");
flag=1;
}
}
// if flag is 0 means there is no
// majority element is present
if (flag==0)
System.out.println("No Majority Element");
}
public static void main (String[] args) {
int arr[] = { 2, 2, 3, 1, 3, 2, 1, 1 };
int n = arr.length;
// Function calling
findMajority(arr, n);
}
}
// This code is contributed by Aman Chowdhury
Python3
# Python3 program to find Majority element in an array
# Function to find Majority element
# in an array
def findMajority(arr, n):
flag = 0
for i in range(n):
count = 0
for j in range(i, n):
if (arr[i] == arr[j]):
count+=1
# If count is greater than n/3 means
# current element is majority element
if (count > int(n / 3)):
print(arr[i], end = " ")
flag = 1
# If flag is 0 means there is no
# majority element is present
if (flag == 0):
print("No Majority Element")
arr = [ 2, 2, 3, 1, 3, 2, 1, 1 ]
n = len(arr)
# Function calling
findMajority(arr, n)
# This code is contributed by mukesh07.
C#
// C# program to find Majority
// element in an array
using System;
using System.Collections.Generic;
class GFG {
// Function to find Majority element
// in an array
static void findMajority(int[] arr, int n)
{
int flag = 0;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = i; j < n; j++) {
if (arr[i] == arr[j])
count++;
}
// if count is greater than n/3 means
// current element is majority element
if (count > n/3) {
Console.Write(arr[i] + " ");
flag = 1;
}
}
// if flag is 0 means there is no
// majority element is present
if (flag == 0)
Console.Write("No Majority Element");
}
static void Main() {
int[] arr = { 2, 2, 3, 1, 3, 2, 1, 1 };
int n = arr.Length;
// Function calling
findMajority(arr, n);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program to find Majority
// element in an array
// Function to find Majority element
// in an array
function findMajority(arr, n)
{
var flag = 0;
for(var i = 0; i < n; i++)
{
var count = 0;
for(var j = i; j < n; j++)
{
if (arr[i] == arr[j])
count++;
}
// If count is greater than n/3 means
// current element is majority element
if (count > n / 3)
{
document.write(arr[i] + " ");
flag = 1;
}
}
// If flag is 0 means there is no
// majority element is present
if (flag == 0)
{
document.write("No Majority Element");
}
}
// Driver code
var arr = [ 2, 2, 3, 1, 3, 2, 1, 1 ];
var n = arr.length;
// Function calling
findMajority(arr, n);
// This code is contributed by bunnyram19
</script>
Producción
2 1
Análisis de Complejidad:
- Complejidad de tiempo: O(n*n) Se necesita un bucle anidado en el que ambos bucles atraviesen la array de principio a fin, por lo que la complejidad de tiempo es O(n^2).
- Espacio auxiliar: O(1) Como no se requiere espacio adicional para ninguna operación, la complejidad del espacio es constante.
Método 2 (usando Hashmap):
- Enfoque: este método es algo similar al algoritmo de votación de Moore en términos de complejidad de tiempo, pero en este caso, no es necesario el segundo paso del algoritmo de votación de Moore. Pero como siempre, aquí la complejidad del espacio se convierte en O(n).
En Hashmap (par clave-valor), en el valor, mantenga un recuento para cada elemento (clave) y siempre que el recuento sea mayor que la mitad de la longitud de la array, devuelva esa clave (elemento mayoritario).
C++
/* C++ program for finding out majority
element in an array */
#include <bits/stdc++.h>
using namespace std;
void findMajority(int arr[], int size)
{
unordered_map<int, int> m;
for(int i = 0; i < size; i++)
m[arr[i]]++;
int flag = 0;
for(auto i : m)
{
if(i.second > size / 3)
{
flag =1;
cout << i.first << " ";
}
}
if(flag == 0)
cout << "No Majority element" << endl;
}
// Driver code
int main()
{
int arr[] = { 2, 2, 3, 1, 3, 2, 1, 1};
int n = sizeof(arr) / sizeof(arr[0]);
// Function calling
findMajority(arr, n);
return 0;
}
// This code is contributed by Aman Chowdhury
Java
import java.util.HashMap;
/* Program for finding out majority element in an array */
class MajorityElement
{
private static void findMajority(int[] arr)
{
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
int flag=0;
for(int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i])) {
int count = map.get(arr[i]) +1;
if (count > arr.length /3) {
System.out.print(arr[i]+" ");
flag=1;
} else
map.put(arr[i], count);
}
else
map.put(arr[i],1);
}
if(flag==0)
System.out.println(" No Majority element");
}
/* Driver program to test the above functions */
public static void main(String[] args)
{
int a[] = new int[]{2, 2, 3, 1, 3, 2, 1, 1};
findMajority(a);
}
}
// This code is contributed by Aman Chowdhury
Python3
# Python3 program for finding out majority element in an array
def findMajority(arr, size):
m = {}
for i in range(size):
if arr[i] in m:
m[arr[i]] += 1
else:
m[arr[i]] = 1
flag = 0
for i in sorted(m):
if m[i] > int(size / 3):
flag =1
print(i, end = " ")
if flag == 0:
print("No Majority element")
arr = [ 2, 2, 3, 1, 3, 2, 1, 1]
n = len(arr)
# Function calling
findMajority(arr, n)
# This code is contributed by rameshtravel07.
C#
/* C# program for finding out majority
element in an array */
using System;
using System.Collections.Generic;
class GFG {
static void findMajority(int[] arr, int size)
{
Dictionary<int, int> m = new Dictionary<int, int>();
for(int i = 0; i < size; i++)
{
if(m.ContainsKey(arr[i]))
{
m[arr[i]]++;
}
else{
m[arr[i]] = 1;
}
}
int flag = 0;
List<int> ans = new List<int>();
foreach(KeyValuePair<int, int> i in m)
{
if(i.Value > size / 3)
{
flag =1;
ans.Add(i.Key);
}
}
if(ans.Count > 0)
{
ans.Sort();
for(int i = 0; i < ans.Count; i++)
{
Console.Write(ans[i] + " ");
}
}
if(flag == 0)
Console.WriteLine("No Majority element");
}
static void Main() {
int[] arr = { 2, 2, 3, 1, 3, 2, 1, 1};
int n = arr.Length;
// Function calling
findMajority(arr, n);
}
}
// This code is contributed by decode2207,
Javascript
<script>
/* JavaScript program for finding out majority
element in an array */
function findMajority(arr, size)
{
let m = new Map();
for(let i = 0; i < size; i++)
{
if(m.has(arr[i]) == true){
m.set(arr[i], m.get(arr[i]) + 1);
}
else m.set(arr[i], 1);
}
let flag = 0;
for(let [key, value] of m)
{
if(value > size / 3)
{
flag = 1;
document.write(key, " ");
}
}
if(flag == 0)
document.write("No Majority element","</br>");
}
// Driver code
let arr = [ 2, 2, 3, 1, 3, 2, 1, 1 ];
let n = arr.length;
// Function calling
findMajority(arr, n);
// This code is contributed by shinjanpatra
</script>
Producción
1 2
Análisis de Complejidad:
- Complejidad de tiempo: O(n) Se necesita un recorrido de la array, por lo que la complejidad de tiempo es lineal.
- Espacio auxiliar: O(n) Ya que un hashmap requiere un espacio lineal.
Método 3 (algoritmo de votación de Moore):
La idea se basa en el algoritmo de votación de Moore. Primero encontramos dos candidatos. Luego comprobamos si alguno de estos dos candidatos es realmente mayoría. A continuación se muestra la solución para el enfoque anterior.
C++
// C++ program to find Majority
// element in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find Majority element
// in an array
void findMajority(int arr[], int n){
int count1 = 0, count2 = 0;
int first=INT_MAX, second=INT_MAX;
int flag=0;
for (int i = 0; i < n; i++) {
// if this element is previously seen,
// increment count1.
if (first == arr[i])
count1++;
// if this element is previously seen,
// increment count2.
else if (second == arr[i])
count2++;
else if (count1 == 0) {
count1++;
first = arr[i];
}
else if (count2 == 0) {
count2++;
second = arr[i];
}
// if current element is different from
// both the previously seen variables,
// decrement both the counts.
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
// Again traverse the array and find the
// actual counts.
for (int i = 0; i < n; i++) {
if (arr[i] == first)
count1++;
else if (arr[i] == second)
count2++;
}
if (count1 > n / 3){
cout << first << " ";
flag=1;
}
if (count2 > n / 3){
cout << second << " ";
flag=1;
}
if(flag==0){
cout << "No Majority Element" << endl;
}
}
int main() {
int arr[] = { 2, 2, 3, 1, 3, 2, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function calling
findMajority(arr, n);
return 0;
}
// This code is contributed by Aman Chowdhury
Java
// Java program to find if any element appears
// more than n/3.
class GFG {
static void findMajority(int arr[], int n)
{
int count1 = 0, count2 = 0;
int flag=0;
// take the integers as the maximum
// value of integer hoping the integer
// would not be present in the array
int first = Integer.MIN_VALUE;;
int second = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
// if this element is previously
// seen, increment count1.
if (first == arr[i])
count1++;
// if this element is previously
// seen, increment count2.
else if (second == arr[i])
count2++;
else if (count1 == 0) {
count1++;
first = arr[i];
}
else if (count2 == 0) {
count2++;
second = arr[i];
}
// if current element is different
// from both the previously seen
// variables, decrement both the
// counts.
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
// Again traverse the array and
// find the actual counts.
for (int i = 0; i < n; i++) {
if (arr[i] == first)
count1++;
else if (arr[i] == second)
count2++;
}
if (count1 > n / 3){
System.out.print(first+" ");
flag=1;
}
if (count2 > n / 3){
System.out.print(second+" ");
flag=1;
}
if(flag==0)
System.out.println("No Majority Element");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 2, 2, 3, 1, 3, 2, 1, 1 };
int n = arr.length;
findMajority(arr,n);
}
}
// This code is contributed by Aman Chowdhury
Python3
# Python3 program to find Majority
# element in an array
# Function to find Majority element
# in an array
def findMajority(arr, n):
count1 = 0
count2 = 0
first = 2147483647
second = 2147483647
flag = 0
for i in range(n):
# if this element is previously seen,
# increment count1.
if first == arr[i]:
count1 += 1
# if this element is previously seen,
# increment count2.
elif second == arr[i]:
count2 += 1
elif count1 == 0:
count1 += 1
first = arr[i]
elif count2 == 0:
count2 += 1
second = arr[i]
# if current element is different from
# both the previously seen variables,
# decrement both the counts.
else:
count1 -= 1
count2 -= 1
count1 = 0
count2 = 0
# Again traverse the array and find the
# actual counts.
for i in range(n):
if arr[i] == first:
count1 += 1
elif arr[i] == second:
count2 += 1
if count1 > int(n / 3):
print(first, end = " ")
flag = 1
if count2 > int(n / 3):
print(second, end = " ")
flag = 1
if flag == 0:
print("No Majority Element")
arr = [ 2, 2, 3, 1, 3, 2, 1, 1 ]
n = len(arr)
# Function calling
findMajority(arr, n)
# This code is contributed by divyesh072019.
C#
// C# program to find if any element appears
// more than n/3
using System;
class GFG {
static void findMajority(int[] arr, int n)
{
int count1 = 0, count2 = 0;
int flag = 0;
// take the integers as the maximum
// value of integer hoping the integer
// would not be present in the array
int first = Int32.MinValue;
int second = Int32.MaxValue;
for (int i = 0; i < n; i++)
{
// if this element is previously
// seen, increment count1.
if (first == arr[i])
count1++;
// if this element is previously
// seen, increment count2.
else if (second == arr[i])
count2++;
else if (count1 == 0) {
count1++;
first = arr[i];
}
else if (count2 == 0) {
count2++;
second = arr[i];
}
// if current element is different
// from both the previously seen
// variables, decrement both the
// counts.
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
// Again traverse the array and
// find the actual counts.
for (int i = 0; i < n; i++) {
if (arr[i] == first)
count1++;
else if (arr[i] == second)
count2++;
}
if (count1 > n / 3){
Console.Write(first+" ");
flag=1;
}
if (count2 > n / 3){
Console.Write(second+" ");
flag=1;
}
if(flag==0)
Console.Write("No Majority Element");
}
static void Main() {
int[] arr = { 2, 2, 3, 1, 3, 2, 1, 1 };
int n = arr.Length;
findMajority(arr,n);
}
}
// This code is contributed by suresh07.
Javascript
<script>
// JavaScript program to find Majority
// element in an array
// Function to find Majority element
// in an array
function findMajority(arr, n) {
var count1 = 0,
count2 = 0;
var first = 2147483647,
second = 2147483647;
var flag = 0;
for (var i = 0; i < n; i++) {
// if this element is previously seen,
// increment count1.
if (first === arr[i]) count1++;
// if this element is previously seen,
// increment count2.
else if (second === arr[i]) count2++;
else if (count1 === 0) {
count1++;
first = arr[i];
} else if (count2 === 0) {
count2++;
second = arr[i];
}
// if current element is different from
// both the previously seen variables,
// decrement both the counts.
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
// Again traverse the array and find the
// actual counts.
for (var i = 0; i < n; i++) {
if (arr[i] === first) count1++;
else if (arr[i] === second) count2++;
}
if (count1 > n / 3) {
document.write(first + " ");
flag = 1;
}
if (count2 > n / 3) {
document.write(second + " ");
flag = 1;
}
if (flag === 0) {
document.write("No Majority Element" + "<br>");
}
}
var arr = [2, 2, 3, 1, 3, 2, 1, 1];
var n = arr.length;
// Function calling
findMajority(arr, n);
</script>
Producción
2 1
Análisis de Complejidad:
- Complejidad de tiempo: O(n) El primer paso del algoritmo realiza un recorrido completo sobre la array que contribuye a O(n) y se consume otro O(n) para verificar si count1 y count2 son mayores que el piso (n/3) veces.
- Espacio auxiliar: O(1) Como no se requiere espacio adicional, la complejidad del espacio es constante
Método 4:
Planteamiento: Para resolver el problema, la idea es utilizar la técnica Divide and Conquer . Siga los pasos a continuación para resolver el problema:
- Inicialice una función MajorElement() que devolverá el recuento de elementos mayoritarios en la array desde cualquier índice de izquierda a derecha .
- Divide la array dada arr[] en dos mitades y pásala repetidamente a la función mostElement() .
- Inicialice bajo y alto como 0 y (N – 1) respectivamente.
- Calcule el elemento mayoritario siguiendo los siguientes pasos:
- Si bajo = alto: Devuelve arr[bajo] como elemento mayoritario.
- Encuentre el índice medio, digamos medio (= (bajo + alto)/2 ).
- Llame recursivamente a los subarreglos izquierdo y derecho como elemento mayoritario (arr, bajo, medio) y elemento mayoritario (arr, medio + 1, alto) .
- Después de completar los pasos anteriores, combine ambos subarreglos y devuelva el elemento mayoritario.
- Siempre que se encuentre el elemento mayoritario requerido, añádalo a la lista resultante.
- Imprime todos los elementos mayoritarios almacenados en la lista.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program for the above approach class Solution: # Function to find all elements that # occurs >= N/3 times in the array def majorityElement(self, a): # If array is empty return # empty list if not a: return [] # Function to find the majority # element by Divide and Conquer def divideAndConquer(lo, hi): if lo == hi: return [a[lo]] # Find mid mid = lo + (hi - lo)//2 # Call to the left half left = divideAndConquer(lo, mid) # Call to the right half right = divideAndConquer(mid + 1, hi) # Stores the result result = [] for numbers in left: if numbers not in right: result.append(numbers) result.extend(right) # Stores all majority elements ans = [] for number in result: count = 0 # Count of elements that # occurs most for index in range(lo, hi + 1): if a[index] == number: count += 1 # If the number is a # majority element if count > (hi - lo + 1)//3: ans.append(number) # Return the list of element return ans # Function Call print(divideAndConquer(0, len(a) - 1)) # Driver Code if __name__ == "__main__": # Given array a[] a = [7, 7, 7, 3, 4, 4, 4, 6] object = Solution() # Function Call object.majorityElement(a)
Producción
[7, 4]
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(log N)
Otro enfoque: usar las funciones integradas de Python:
- Cuente las frecuencias de cada elemento usando la función Counter().
- Recorra la array de frecuencias e imprima todos los elementos que ocurren en más de n/3 veces.
A continuación se muestra la implementación:
Python3
# Python3 program for the above approach from collections import Counter # Function to find the number of array # elements with frequency more than n/3 times def printElements(arr, n): # Calculating n/3 x = n//3 # Counting frequency of every element using Counter mp = Counter(arr) # Traverse the map and print all # the elements with occurrence atleast n/3 times for it in mp: if mp[it] > x: print(it, end=" ") # Driver code arr = [7, 7, 7, 3, 4, 4, 4, 6] # Size of array n = len(arr) # Function Call printElements(arr, n) # This code is contributed by vikkycirus
Producción
7 4
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por BIRANCHINARAYANPADHI y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA