Dada una array de n números y un entero positivo k . El problema es encontrar k números con la mayor cantidad de ocurrencias, es decir, los k números superiores que tienen la máxima frecuencia. Si dos números tienen la misma frecuencia, se debe dar preferencia al número mayor. Los números deben mostrarse en orden decreciente de sus frecuencias. Se supone que la array consta de k números con la mayoría de las ocurrencias.
Ejemplos:
Entrada:
arr[] = {3, 1, 4, 4, 5, 2, 6, 1},
k = 2
Salida: 4 1
Explicación:
Frecuencia de 4 = 2
Frecuencia de 1 = 2
Estos dos tienen la frecuencia máxima y
4 es mayor que 1 .Entrada:
arr[] = {7, 10, 11, 5, 2, 5, 5, 7, 11, 8, 9}, k = 4 Salida:
5
11 7 10
Explicación:
Frecuencia de 5 = 3
Frecuencia de 11 = 2
Frecuencia de 7 = 2
Frecuencia de 10 = 1
Estos cuatro tienen la frecuencia máxima y
5 es el más grande entre el resto.
Preguntado en la entrevista de Amazon
Método 1:
- Enfoque: el proceso de pensamiento debe comenzar con la creación de un HashMap para almacenar el par elemento-frecuencia en el HashMap. HashMap se utiliza para realizar la inserción y actualización en tiempo constante. Luego ordene el par elemento-frecuencia en orden decreciente de frecuencia. Esto brinda información sobre cada elemento y la cantidad de veces que están presentes en la array. Para obtener k elementos de la array, imprima los primeros k elementos de la array ordenada.
- Hashmap: HashMap es parte de la colección de Java desde Java 1.2. Proporciona la implementación básica de la interfaz Map de Java. Almacena los datos en pares (Clave, Valor). Para acceder a un valor se debe conocer su clave. HashMap se conoce como HashMap porque utiliza una técnica llamada Hashing. Hashing es una técnica de convertir una string grande en una string pequeña que representa la misma string. Un valor más corto ayuda en la indexación y búsquedas más rápidas. HashSet también usa HashMap internamente. Utiliza internamente una lista de enlaces para almacenar pares clave-valor ya explicados en detalle en HashSet y otros artículos.
Más sobre HashMap >> - Algoritmo:
- Cree un Hashmap hm , para almacenar el par clave-valor, es decir, el par elemento-frecuencia.
- Atraviesa la array de principio a fin.
- Para cada elemento de la array, actualice hm[array[i]]++
- Almacene el par elemento-frecuencia en un vector y ordene el vector en orden decreciente de frecuencia.
- Imprime los primeros k elementos de la array ordenada.
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ implementation to find k numbers with most
// occurrences in the given array
#include <bits/stdc++.h>
using namespace std;
// comparison function to sort the 'freq_arr[]'
bool compare(pair<int, int> p1, pair<int, int> p2)
{
// if frequencies of two elements are same
// then the larger number should come first
if (p1.second == p2.second)
return p1.first > p2.first;
// sort on the basis of decreasing order
// of frequencies
return p1.second > p2.second;
}
// function to print the k numbers with most occurrences
void print_N_mostFrequentNumber(int arr[], int n, int k)
{
// unordered_map 'um' implemented as frequency hash table
unordered_map<int, int> um;
for (int i = 0; i < n; i++)
um[arr[i]]++;
// store the elements of 'um' in the vector 'freq_arr'
vector<pair<int, int> > freq_arr(um.begin(), um.end());
// sort the vector 'freq_arr' on the basis of the
// 'compare' function
sort(freq_arr.begin(), freq_arr.end(), compare);
// display the top k numbers
cout << k << " numbers with most occurrences are:\n";
for (int i = 0; i < k; i++)
cout << freq_arr[i].first << " ";
}
// Driver program to test above
int main()
{
int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
print_N_mostFrequentNumber(arr, n, k);
return 0;
}
Java
// Java implementation to find
// k elements with max occurrence.
import java.util.*;
public class KFrequentNumbers
{
static void print_N_mostFrequentNumber(int[] arr,
int n,
int k)
{
Map<Integer, Integer> mp
= new HashMap<Integer, Integer>();
// Put count of all the
// distinct elements in Map
// with element as the key &
// count as the value.
for (int i = 0; i < n; i++) {
// Get the count for the
// element if already present in the
// Map or get the default value which is 0.
mp.put(arr[i],
mp.getOrDefault(arr[i], 0) + 1);
}
// Create a list from elements of HashMap
List<Map.Entry<Integer, Integer> > list
= new ArrayList<Map.Entry<Integer,
Integer> >(
mp.entrySet());
// Sort the list
Collections.sort(
list,
new Comparator<Map.Entry<Integer,
Integer> >()
{
public int compare(
Map.Entry<Integer, Integer> o1,
Map.Entry<Integer, Integer> o2)
{
if (o1.getValue() == o2.getValue())
return o2.getKey() - o1.getKey();
else
return o2.getValue()
- o1.getValue();
}
});
for (int i = 0; i < k; i++)
System.out.println(list.get(i).getKey());
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 };
int n = arr.length;
int k = 2;
// Function call
print_N_mostFrequentNumber(arr, n, k);
}
}
Python3
# Python3 implementation to find k numbers
# with most occurrences in the given array
# function to print the k numbers with
# most occurrences
def pr_N_mostFrequentNumber(arr, n, k):
um = {}
for i in range(n):
if arr[i] in um:
um[arr[i]] += 1
else:
um[arr[i]] = 1
a = [0] * (len(um))
j = 0
for i in um:
a[j] = [i, um[i]]
j += 1
a = sorted(a, key=lambda x: x[0],
reverse=True)
a = sorted(a, key=lambda x: x[1],
reverse=True)
# display the top k numbers
print(k, "numbers with most occurrences are:")
for i in range(k):
print(a[i][0], end=" ")
# Driver code
if __name__ == "__main__":
arr = [3, 1, 4, 4, 5, 2, 6, 1]
n = 8
k = 2
pr_N_mostFrequentNumber(arr, n, k)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# implementation to find
// k elements with max occurrence.
using System;
using System.Collections.Generic;
public class Comparer : IComparer<KeyValuePair<int, int> > {
public int Compare(KeyValuePair<int, int> p2,
KeyValuePair<int, int> p1)
{
// if frequencies of two elements are same
// then the larger number should come first
if (p1.Value == p2.Value)
return p1.Key.CompareTo(p2.Key);
// sort on the basis of decreasing order
// of frequencies
return p1.Value.CompareTo(p2.Value);
}
}
public class KFrequentNumbers {
static void print_N_mostFrequentNumber(int[] arr, int n,
int k)
{
IDictionary<int, int> um
= new Dictionary<int, int>();
// Put count of all the
// distinct elements in Map
// with element as the key &
// count as the value.
for (int i = 0; i < n; i++) {
// Get the count for the
// element if already present in the
// Map or get the default value which is 0
if (um.ContainsKey(arr[i]))
um[arr[i]] += 1;
else
um[arr[i]] = 1;
}
// Create a list from elements of HashMap
List<KeyValuePair<int, int> > list
= new List<KeyValuePair<int, int> >();
foreach(KeyValuePair<int, int> entry in um)
{
list.Add(entry);
}
// Sort the list
Comparer compare = new Comparer();
list.Sort(compare);
for (int i = 0; i < k; i++)
Console.Write(list[i].Key + " ");
}
public static void Main(string[] args)
{
int[] arr = { 3, 1, 4, 4, 5, 2, 6, 1 };
int n = arr.Length;
int k = 2;
Console.Write(
k + " elements with most occurrences are:\n");
// Function call
print_N_mostFrequentNumber(arr, n, k);
}
}
// this code is contributed by phasing17
Javascript
<script>
// JavaScript implementation to find
// k elements with max occurrence.
function print_N_mostFrequentNumber(arr, n, k) {
let mp = new Map();
// Put count of all the
// distinct elements in Map
// with element as the key &
// count as the value.
for (let i = 0; i < n; i++) {
// Get the count for the
// element if already present in the
// Map or get the default value which is 0.
if (mp.has(arr[i])) {
mp.set(arr[i], mp.get(arr[i]) + 1)
} else {
mp.set(arr[i], 1)
}
}
// Create a list from elements of HashMap
let list = [...mp];
// Sort the list
list.sort((o1, o2) => {
if (o1[1] == o2[1])
return o2[0] - o1[0];
else
return o2[1] - o1[1];
})
document.write(k + " numbers with most occurrences are:<br>");
for (let i = 0; i < k; i++)
document.write(list[i][0] + " ");
}
// Driver Code
let arr = [3, 1, 4, 4, 5, 2, 6, 1];
let n = arr.length;
let k = 2;
// Function call
print_N_mostFrequentNumber(arr, n, k); 1
</script>
Producción
2 numbers with most occurrences are: 4 1
Análisis de Complejidad:
- Complejidad de tiempo: O (d log d), donde d es el recuento de elementos distintos en la array. Para ordenar la array O(d log d) se necesita tiempo.
- Espacio auxiliar: O(d), donde d es el recuento de elementos distintos en la array. Para almacenar los elementos en HashMap O(d) se necesita complejidad espacial.
Método 2:
- Enfoque: Cree un HashMap para almacenar el par elemento-frecuencia en el HashMap. HashMap se utiliza para realizar la inserción y actualización en tiempo constante. Luego use una cola de prioridad para almacenar el par elemento-frecuencia ( Max-Heap ). Esto da el elemento que tiene la frecuencia máxima en la raíz de la cola de prioridad. Quite la parte superior o la raíz de Priority Queue K veces e imprima el elemento. Para insertar y eliminar la parte superior de la cola de prioridad se requiere tiempo O (log n) .
Cola de prioridad:Las colas de prioridad son un tipo de adaptadores de contenedores, diseñados específicamente de modo que el primer elemento de la cola es el mayor de todos los elementos de la cola y los elementos están en orden no creciente (por lo tanto, podemos ver que cada elemento de la cola tiene una prioridad{ orden fijo}).
Más información sobre Priority Queue: C++ STL Priority_queue - Algoritmo:
- Cree un Hashmap hm , para almacenar el par clave-valor, es decir, el par elemento-frecuencia.
- Atraviesa la array de principio a fin.
- Para cada elemento de la array, actualice hm[array[i]]++
- Almacene el par elemento-frecuencia en una Cola de prioridad y cree la Cola de prioridad, esto lleva O(n) tiempo.
- Ejecute un bucle k veces y, en cada iteración, elimine la parte superior de la cola de prioridad e imprima el elemento.
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ implementation to find k numbers with most
// occurrences in the given array
#include <bits/stdc++.h>
using namespace std;
// comparison function defined for the priority queue
struct compare {
bool operator()(pair<int, int> p1, pair<int, int> p2)
{
// if frequencies of two elements are same
// then the larger number should come first
if (p1.second == p2.second)
return p1.first < p2.first;
// insert elements in the priority queue on the basis of
// decreasing order of frequencies
return p1.second < p2.second;
}
};
// function to print the k numbers with most occurrences
void print_N_mostFrequentNumber(int arr[], int n, int k)
{
// unordered_map 'um' implemented as frequency hash table
unordered_map<int, int> um;
for (int i = 0; i < n; i++)
um[arr[i]]++;
// priority queue 'pq' implemented as max heap on the basis
// of the comparison operator 'compare'
// element with the highest frequency is the root of 'pq'
// in case of conflicts, larger element is the root
priority_queue<pair<int, int>, vector<pair<int, int> >,
compare>
pq(um.begin(), um.end());
// display the top k numbers
cout << k << " numbers with most occurrences are:\n";
for (int i = 1; i <= k; i++) {
cout << pq.top().first << " ";
pq.pop();
}
}
// Driver program to test above
int main()
{
int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
print_N_mostFrequentNumber(arr, n, k);
return 0;
}
Java
// Java implementation to find k
// elements with max occurrence.
import java.util.*;
public class KFrequentNumbers {
static void print_N_mostFrequentNumber(int[] arr,
int n,
int k)
{
Map<Integer, Integer> mp
= new HashMap<Integer, Integer>();
// Put count of all the
// distinct elements in Map
// with element as the key &
// count as the value.
for (int i = 0; i < n; i++) {
// Get the count for the
// element if already
// present in the Map or
// get the default value
// which is 0.
mp.put(arr[i],
mp.getOrDefault(arr[i], 0) + 1);
}
// Create a Priority Queue
// to sort based on the
// count or on the key if the
// count is same
PriorityQueue<Map.Entry<Integer,
Integer>> queue
= new PriorityQueue<>(
(a, b)
-> a.getValue().equals(b.getValue())
? Integer.compare(b.getKey(),
a.getKey())
: Integer.compare(b.getValue(),
a.getValue()));
// Insert the data from the map
// to the Priority Queue.
for (Map.Entry<Integer, Integer> entry :
mp.entrySet())
queue.offer(entry);
// Print the top k elements
for (int i = 0; i < k; i++)
{
System.out.println(queue.poll().getKey());
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 };
int n = arr.length;
int k = 2;
// Function call
print_N_mostFrequentNumber(arr, n, k);
}
}
// This code is contributed by Shubham Kumar Shah
Python3
# Python3 implementation to find k # numbers with most occurrences in # the given array import heapq # Function to print the k numbers with # most occurrences def print_N_mostFrequentNumber(arr, n, k): mp = dict() # Put count of all the distinct elements # in dictionary with element as the # key & count as the value. for i in range(0, n): if arr[i] not in mp: mp[arr[i]] = 0 else: mp[arr[i]] += 1 # Using heapq data structure heap = [(value, key) for key, value in mp.items()] # Get the top k elements largest = heapq.nlargest(k, heap) # Insert the data from the map to # the priority queue print(k, " numbers with most " "occurrences are:", sep = "") # Print the top k elements for i in range(k): print(largest[i][1], end =" ") # Driver code if __name__=="__main__": arr = [ 3, 1, 4, 4, 5, 2, 6, 1 ] n = len(arr) k = 2 print_N_mostFrequentNumber(arr, n, k) # This code is contributed by MuskanKalra1
C#
// C# implementation to find k
// elements with max occurrence.
using System;
using System.Collections.Generic;
using System.Linq;
public class KFrequentNumbers {
static void print_N_mostFrequentNumber(int[] arr, int n,
int k)
{
Dictionary<int, int> mp
= new Dictionary<int, int>();
// Put count of all the
// distinct elements in Map
// with element as the key &
// count as the value.
for (int i = 0; i < n; i++) {
// Get the count for the
// element if already
// present in the Map or
// get the default value
// which is 0.
if (!mp.ContainsKey(arr[i]))
mp[arr[i]] = 0;
mp[arr[i]]++;
}
// Create a Priority Queue
// to sort based on the
// count or on the key if the
// count is same
List<int> queue = mp.Keys.ToList();
queue.Sort(delegate(int y, int x) {
if (mp[x] == mp[y])
return x.CompareTo(y);
else
return (mp[x]).CompareTo(mp[y]);
});
// Print the top k elements
Console.WriteLine(
k + " numbers with the most occurrences are:");
for (int i = 0; i < k; i++) {
Console.WriteLine(queue[i] + " ");
}
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 3, 1, 4, 4, 5, 2, 6, 1 };
int n = arr.Length;
int k = 2;
// Function call
print_N_mostFrequentNumber(arr, n, k);
}
}
// This code is contributed by phasing17
Javascript
<script>
// Javascript implementation to find k
// elements with max occurrence.
function print_N_mostFrequentNumber(arr,n,k)
{
let mp=new Map();
// Put count of all the
// distinct elements in Map
// with element as the key &
// count as the value.
for (let i = 0; i < n; i++) {
// Get the count for the
// element if already
// present in the Map or
// get the default value
// which is 0.
if(!mp.has(arr[i]))
mp.set(arr[i],0);
mp.set(arr[i],
mp.get(arr[i]) + 1);
}
// Create a Priority Queue
// to sort based on the
// count or on the key if the
// count is same
let queue=[...mp];
queue.sort(function(a,b){
if(a[1]==b[1])
{
return b[0]-a[0];
}
else
{
return b[1]-a[1];
}
});
document.write(k+" numbers with most "+"occurrences are:<br>")
for(let i=0;i<k;i++)
{
document.write(queue[i][0]+" ");
}
}
// Driver Code
let arr=[3, 1, 4, 4, 5, 2, 6, 1 ];
let n = arr.length;
let k = 2;
// Function call
print_N_mostFrequentNumber(arr, n, k);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
2 numbers with most occurrences are: 4 1
Análisis de Complejidad:
- Complejidad de tiempo: O(k log d + d), donde d es el recuento de elementos distintos en la array.
Para eliminar la parte superior de la cola de prioridad se requiere un tiempo O (log d), por lo que si se eliminan k elementos, entonces se requiere un tiempo O (k log d) y para atravesar los distintos elementos se requiere un tiempo O (d). - Espacio auxiliar: O(d), donde d es el recuento de elementos distintos en la array.
Para almacenar los elementos en HashMap O(d) se necesita complejidad espacial.
Encuentre k más frecuente en tiempo lineal
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA