Dada una array, encuentre el elemento más frecuente en ella. Si hay varios elementos que aparecen un número máximo de veces, imprima cualquiera de ellos.
Ejemplos:
Entrada: arr[] = {1, 3, 2, 1, 4, 1}
Salida: 1
Explicación: 1 aparece tres veces en la array, que es la frecuencia máxima.Entrada: arr[] = {10, 20, 10, 20, 30, 20, 20}
Salida: 20
Una solución simple es ejecutar dos bucles. El bucle exterior recoge todos los elementos uno por uno. El bucle interno encuentra la frecuencia del elemento seleccionado y lo compara con el máximo hasta el momento.
C++
// CPP program to find the most frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;
int mostFrequent(int *arr, int n) {
// code here
int maxcount=0;
int element_having_max_freq;
for(int i=0;i<n;i++)
{
int count=0;
for(int j=0;j<n;j++)
{
if(arr[i] == arr[j])
count++;
}
if(count>maxcount)
{
maxcount=count;
element_having_max_freq = arr[i];
}
}
return element_having_max_freq;
}
// Driver program
int main()
{
int arr[] = { 40,50,30,40,50,30,30};
int n = sizeof(arr) / sizeof(arr[0]);
cout << mostFrequent(arr, n);
return 0;
}
// This code is contributed by Arpit Jain
Java
public class GFG
{
// Java program to find the most frequent element
// in an array.
public static int mostFrequent(int[] arr, int n)
{
int maxcount = 0;
int element_having_max_freq = 0;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j]) {
count++;
}
}
if (count > maxcount) {
maxcount = count;
element_having_max_freq = arr[i];
}
}
return element_having_max_freq;
}
// Driver program
public static void main(String[] args)
{
int[] arr = { 40, 50, 30, 40, 50, 30, 30 };
int n = arr.length;
System.out.print(mostFrequent(arr, n));
}
}
// This code is contributed by Aarti_Rathi
Python3
# Python3 program to find the most # frequent element in an array. def mostFrequent(arr, n): maxcount = 0; element_having_max_freq = 0; for i in range(0, n): count = 0 for j in range(0, n): if(arr[i] == arr[j]): count += 1 if(count > maxcount): maxcount = count element_having_max_freq = arr[i] return element_having_max_freq; # Driver Code arr = [40,50,30,40,50,30,30] n = len(arr) print(mostFrequent(arr, n)) # This code is contributed by Arpit Jain
C#
// C# program to find the most frequent element
// in an array
using System;
public class GFG
{
// C# program to find the most frequent element
// in an array.
public static int mostFrequent(int[] arr, int n)
{
int maxcount = 0;
int element_having_max_freq = 0;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j]) {
count++;
}
}
if (count > maxcount) {
maxcount = count;
element_having_max_freq = arr[i];
}
}
return element_having_max_freq;
}
// Driver program
public static void Main(String[] args)
{
int[] arr = { 40, 50, 30, 40, 50, 30, 30 };
int n = arr.Length;
Console.Write(mostFrequent(arr, n));
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Producción
30
La complejidad temporal de esta solución es O(n 2 ) dado que se ejecutan 2 bucles desde i=0 hasta i=n, podemos mejorar su complejidad temporal tomando una array visitada y omitiendo números para los que ya calculamos la frecuencia.
Una mejor solución es hacer la clasificación. Primero ordenamos la array, luego recorremos linealmente la array.
C++
// CPP program to find the most frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;
int mostFrequent(int arr[], int n)
{
// Sort the array
sort(arr, arr + n);
// Find the max frequency using linear traversal
int max_count = 1, res = arr[0], curr_count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1])
curr_count++;
else
curr_count = 1;
if (curr_count > max_count) {
max_count = curr_count;
res = arr[i - 1];
}
}
return res;
}
// Driver program
int main()
{
int arr[] = { 40,50,30,40,50,30,30};
int n = sizeof(arr) / sizeof(arr[0]);
cout << mostFrequent(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// CPP program to find the most frequent element
// in an array.
#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
int mostFrequent(int arr[], int n)
{
// Sort the array
qsort(arr, n, sizeof(int), cmpfunc);
// find the max frequency using linear traversal
int max_count = 1, res = arr[0], curr_count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1])
curr_count++;
else
curr_count = 1;
if (curr_count > max_count) {
max_count = curr_count;
res = arr[i - 1];
}
}
return res;
}
// driver program
int main()
{
int arr[] = { 40,50,30,40,50,30,30};
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", mostFrequent(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find the most frequent element
// in an array
import java.util.*;
class GFG {
static int mostFrequent(int arr[], int n)
{
// Sort the array
Arrays.sort(arr);
// find the max frequency using linear traversal
int max_count = 1, res = arr[0];
int curr_count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1])
curr_count++;
else
curr_count = 1;
if (curr_count > max_count) {
max_count = curr_count;
res = arr[i - 1];
}
}
return res;
}
// Driver program
public static void main(String[] args)
{
int arr[] = { 40,50,30,40,50,30,30};
int n = arr.length;
System.out.println(mostFrequent(arr, n));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to find the most # frequent element in an array. def mostFrequent(arr, n): # Sort the array arr.sort() # find the max frequency using # linear traversal max_count = 1 res = arr[0] curr_count = 1 for i in range(1, n): if (arr[i] == arr[i - 1]): curr_count += 1 else: curr_count = 1 # If last element is most frequent if (curr_count > max_count): max_count = curr_count res = arr[i - 1] return res # Driver Code arr = [40,50,30,40,50,30,30] n = len(arr) print(mostFrequent(arr, n)) # This code is contributed by Smitha Dinesh Semwal.
C#
// C# program to find the most
// frequent element in an array
using System;
class GFG {
static int mostFrequent(int[] arr, int n)
{
// Sort the array
Array.Sort(arr);
// find the max frequency using
// linear traversal
int max_count = 1, res = arr[0];
int curr_count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1])
curr_count++;
else
curr_count = 1;
// If last element is most frequent
if (curr_count > max_count) {
max_count = curr_count;
res = arr[i - 1];
}
}
return res;
}
// Driver code
public static void Main()
{
int[] arr = {40,50,30,40,50,30,30 };
int n = arr.Length;
Console.WriteLine(mostFrequent(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find the
// most frequent element
// in an array.
function mostFrequent( $arr, $n)
{
// Sort the array
sort($arr);
sort($arr , $n);
// find the max frequency
// using linear traversal
$max_count = 1;
$res = $arr[0];
$curr_count = 1;
for ($i = 1; $i < $n; $i++)
{
if ($arr[$i] == $arr[$i - 1])
$curr_count++;
else
$curr_count = 1;
if ($curr_count > $max_count)
{
$max_count = $curr_count;
$res = $arr[$i - 1];
}
}
return $res;
}
// Driver Code
{
$arr = array(40,50,30,40,50,30,30);
$n = sizeof($arr) / sizeof($arr[0]);
echo mostFrequent($arr, $n);
return 0;
}
// This code is contributed by nitin mittal
?>
Javascript
<script>
// JavaScript program to find the most frequent element
//in an array
function mostFrequent(arr, n)
{
// Sort the array
arr.sort();
// find the max frequency using linear
// traversal
let max_count = 1, res = arr[0];
let curr_count = 1;
for (let i = 1; i < n; i++)
{
if (arr[i] == arr[i - 1])
curr_count++;
else
curr_count = 1;
if (curr_count > max_count)
{
max_count = curr_count;
res = arr[i - 1];
}
}
return res;
}
// Driver Code
let arr = [40,50,30,40,50,30,30];
let n = arr.length;
document.write(mostFrequent(arr,n));
// This code is contributed by code_hunt.
</script>
Producción
30
Complejidad de tiempo: O(nlog(n))
Espacio auxiliar: O(1)
Una solución eficiente es usar hashing. Creamos una tabla hash y almacenamos elementos y su frecuencia cuenta como pares clave-valor. Finalmente, recorremos la tabla hash e imprimimos la clave con el valor máximo.
C++
// CPP program to find the most frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;
int mostFrequent(int arr[], int n)
{
// Insert all elements in hash.
unordered_map<int, int> hash;
for (int i = 0; i < n; i++)
hash[arr[i]]++;
// find the max frequency
int max_count = 0, res = -1;
for (auto i : hash) {
if (max_count < i.second) {
res = i.first;
max_count = i.second;
}
}
return res;
}
// driver program
int main()
{
int arr[] = {40,50,30,40,50,30,30 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << mostFrequent(arr, n);
return 0;
}
Java
//Java program to find the most frequent element
//in an array
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
class GFG {
static int mostFrequent(int arr[], int n)
{
// Insert all elements in hash
Map<Integer, Integer> hp =
new HashMap<Integer, Integer>();
for(int i = 0; i < n; i++)
{
int key = arr[i];
if(hp.containsKey(key))
{
int freq = hp.get(key);
freq++;
hp.put(key, freq);
}
else
{
hp.put(key, 1);
}
}
// find max frequency.
int max_count = 0, res = -1;
for(Entry<Integer, Integer> val : hp.entrySet())
{
if (max_count < val.getValue())
{
res = val.getKey();
max_count = val.getValue();
}
}
return res;
}
// Driver code
public static void main (String[] args) {
int arr[] = {40,50,30,40,50,30,30};
int n = arr.length;
System.out.println(mostFrequent(arr, n));
}
}
// This code is contributed by Akash Singh.
Python3
# Python3 program to find the most # frequent element in an array. import math as mt def mostFrequent(arr, n): # Insert all elements in Hash. Hash = dict() for i in range(n): if arr[i] in Hash.keys(): Hash[arr[i]] += 1 else: Hash[arr[i]] = 1 # find the max frequency max_count = 0 res = -1 for i in Hash: if (max_count < Hash[i]): res = i max_count = Hash[i] return res # Driver Code arr = [ 40,50,30,40,50,30,30] n = len(arr) print(mostFrequent(arr, n)) # This code is contributed # by Mohit kumar 29
C#
// C# program to find the most
// frequent element in an array
using System;
using System.Collections.Generic;
class GFG
{
static int mostFrequent(int []arr,
int n)
{
// Insert all elements in hash
Dictionary<int, int> hp =
new Dictionary<int, int>();
for (int i = 0; i < n; i++)
{
int key = arr[i];
if(hp.ContainsKey(key))
{
int freq = hp[key];
freq++;
hp[key] = freq;
}
else
hp.Add(key, 1);
}
// find max frequency.
int min_count = 0, res = -1;
foreach (KeyValuePair<int,
int> pair in hp)
{
if (min_count < pair.Value)
{
res = pair.Key;
min_count = pair.Value;
}
}
return res;
}
// Driver code
static void Main ()
{
int []arr = new int[]{40,50,30,40,50,30,30};
int n = arr.Length;
Console.Write(mostFrequent(arr, n));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Javascript
<script>
// Javascript program to find
// the most frequent element
// in an array.
function mostFrequent(arr, n)
{
// Insert all elements in hash.
var hash = new Map();
for (var i = 0; i < n; i++)
{
if(hash.has(arr[i]))
hash.set(arr[i], hash.get(arr[i])+1)
else
hash.set(arr[i], 1)
}
// find the max frequency
var max_count = 0, res = -1;
hash.forEach((value,key) => {
if (max_count < value) {
res = key;
max_count = value;
}
});
return res;
}
// driver program
var arr = [40,50,30,40,50,30,30];
var n = arr.length;
document.write( mostFrequent(arr, n));
</script>
Producción
30
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Una solución eficiente a este problema puede ser resolver este problema mediante el algoritmo de votación de Moore.
NOTA: EL ALGORITMO DE VOTACIÓN ANTERIOR SOLO FUNCIONA CUANDO EL ELEMENTO MÁXIMO QUE OCURRE ES MÁS DE (SIZEOFARRAY/2) VECES;
En este método, encontraremos el entero máximo ocurrido contando los votos que tiene un número.
C++
#include <iostream>
using namespace std;
int maxFreq(int *arr, int n) {
//using moore's voting algorithm
int res = 0;
int count = 1;
for(int i = 1; i < n; i++) {
if(arr[i] == arr[res]) {
count++;
} else {
count--;
}
if(count == 0) {
res = i;
count = 1;
}
}
return arr[res];
}
int main()
{
int arr[] = {40,50,30,40,50,30,30};
int n = sizeof(arr) / sizeof(arr[0]);
int freq = maxFreq(arr , n);
int count = 0;
for(int i = 0; i < n; i++) {
if(arr[i] == freq) {
count++;
}
}
cout <<"Element " << maxFreq(arr , n) << " occurs " << count << " times" << endl;;
return 0;
//This code is contributed by Ashish Kumar Shakya
}
Java
import java.io.*;
class GFG
{
static int maxFreq(int []arr, int n)
{
// using moore's voting algorithm
int res = 0;
int count = 1;
for(int i = 1; i < n; i++) {
if(arr[i] == arr[res]) {
count++;
} else {
count--;
}
if(count == 0) {
res = i;
count = 1;
}
}
return arr[res];
}
// Driver code
public static void main (String[] args) {
int arr[] = {40,50,30,40,50,30,30};
int n = arr.length;
int freq = maxFreq(arr , n);
int count = 0;
for(int i = 0; i < n; i++) {
if(arr[i] == freq) {
count++;
}
}
System.out.println("Element " +maxFreq(arr , n) +" occurs " +count +" times" );
}
}
// This code is contributed by shivanisinghss2110
Python3
def maxFreq(arr, n):
# Using moore's voting algorithm
res = 0
count = 1
for i in range(1, n):
if (arr[i] == arr[res]):
count += 1
else:
count -= 1
if (count == 0):
res = i
count = 1
return arr[res]
# Driver code
arr = [ 40, 50, 30, 40, 50, 30, 30 ]
n = len(arr)
freq = maxFreq(arr, n)
count = 0
for i in range (n):
if(arr[i] == freq):
count += 1
print("Element ", maxFreq(arr , n),
" occurs ", count, " times")
# This code is contributed by shivanisinghss2110
C#
using System;
class GFG
{
static int maxFreq(int []arr, int n)
{
// using moore's voting algorithm
int res = 0;
int count = 1;
for(int i = 1; i < n; i++) {
if(arr[i] == arr[res]) {
count++;
} else {
count--;
}
if(count == 0) {
res = i;
count = 1;
}
}
return arr[res];
}
// Driver code
public static void Main (String[] args) {
int []arr = {40,50,30,40,50,30,30};
int n = arr.Length;
int freq = maxFreq(arr , n);
int count = 0;
for(int i = 0; i < n; i++) {
if(arr[i] == freq) {
count++;
}
}
Console.Write("Element " +maxFreq(arr , n) +" occurs " +count +" times" );
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
function maxFreq(arr, n) {
//using moore's voting algorithm
var res = 0;
var count = 1;
for (var i = 1; i < n; i++) {
if (arr[i] === arr[res]) {
count++;
} else {
count--;
}
if (count === 0) {
res = i;
count = 1;
}
}
return arr[res];
}
var arr = [40, 50, 30, 40, 50, 30, 30];
var n = arr.length;
var freq = maxFreq(arr, n);
var count = 0;
for (var i = 0; i < n; i++) {
if (arr[i] === freq) {
count++;
}
}
document.write(
"Element " + maxFreq(arr, n) + " occurs " +
count + " times" + "<br>"
);
</script>
Producción
Element 30 occurs 3 times
Complejidad temporal: O(n)
Espacio auxiliar: O(1)