Dada una array de enteros, necesitamos imprimir los k elementos más frecuentes. Si hay empate, debemos preferir los elementos cuya primera aparición es la primera.
Ejemplos:
Entrada: arr[] = {10, 5, 20, 5, 10, 10, 30}, k = 2
Salida: 10 5Entrada: arr[] = {7, 7, 6, 6, 6, 7, 5, 4, 4, 10, 5}, k = 3
Salida: 7 6 5
Explicación:
En este ejemplo, 7 y 6 tienen el mismo frecuencias Imprimimos 7 primero porque la primera aparición de 7 es primero. De manera similar, 5 y 4 tienen las mismas frecuencias. Preferimos 5 porque la primera aparición de 5 es la primera.
Hemos discutido dos métodos en la publicación a continuación.
Encuentre k números con la mayor cantidad de ocurrencias en la array dada
Primero hablemos de una solución simple que se imprime en cualquier orden en el caso de un empate. Luego discutiremos la solución que toma del pedido.
La idea es usar hashing con indexación de frecuencia. Primero almacenamos los recuentos en un hash. Luego recorremos el hash y usamos frecuencias como índice para almacenar elementos con frecuencias dadas. El factor importante aquí es que la frecuencia máxima puede ser n. Entonces, una array de tamaño n+1 sería buena.
C++
// C++ implementation to find k numbers with most
// occurrences in the given array
#include <bits/stdc++.h>
using namespace std;
// 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]]++;
// Use frequencies as indexes and put
// elements with given frequency in a
// vector (related to a frequency)
vector<int> freq[n + 1];
for (auto x : um)
freq[x.second].push_back(x.first);
// Initialize count of items printed
int count = 0;
// Traverse the frequency array from
// right side as we need the most
// frequent items.
for (int i = n; i >= 0; i--) {
// Print items of current frequency
for (int x : freq[i]) {
cout << x << " ";
count++;
if (count == k)
return;
}
}
}
// 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);
}
// Initialize an array list of array lists
List<List<Integer> > freq = new ArrayList<List<Integer> >();
for (int i = 0; i <= n; i++)
freq.add(new ArrayList<Integer>());
// Use frequencies as indexes and add corresponding
// values to the list
for (Map.Entry<Integer, Integer> x : mp.entrySet())
freq.get(x.getValue()).add(x.getKey());
// Traverse freq[] from right side.
int count = 0;
for (int i = n; i >= 0; i--) {
for (int x : freq.get(i)) {
System.out.println(x);
count++;
if (count == k)
return;
}
}
}
// Driver Code to test the code.
public static void main(String[] args)
{
int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 };
int n = arr.length;
int k = 2;
print_N_mostFrequentNumber(arr, n, k);
}
}
Python3
# Python3 implementation to find k numbers
# with most occurrences in the given array
# Function to print k numbers with most occurrences
def print_N_mostFrequentNumber(arr, n, k):
# unordered_map 'um' implemented as
# frequency hash table
um = {}
for i in range(n):
um[arr[i]] = um.get(arr[i], 0) + 1
# Use frequencies as indexes and put
# elements with given frequency in a
# vector (related to a frequency)
freq = [[] for i in range(n + 1)]
for x in um:
freq[um[x]].append(x)
# Initialize count of items printed
count = 0
# Traverse the frequency array from
# right side as we need the most
# frequent items.
for i in range(n, -1, -1):
# Print items of current frequency
for x in sorted(freq[i])[::-1]:
print(x, end = " ")
count += 1
if (count == k):
return
# 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 mohit kumar 29
C#
// C# implementation to find
// k elements with max occurrence.
using System;
using System.Collections.Generic;
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]] = mp[arr[i]] + 1;
}
else
{
mp.Add(arr[i], 1);
}
}
// Initialize an array
// list of array lists
List<List<int> > freq =
new List<List<int> >();
for (int i = 0; i <= n; i++)
freq.Add(new List<int>());
// Use frequencies as indexes
// and add corresponding
// values to the list
foreach (KeyValuePair<int,
int> x in mp)
freq[x.Value].Add(x.Key);
// Traverse []freq from
// right side.
int count = 0;
for (int i = n; i >= 0; i--)
{
foreach (int x in freq[i])
{
Console.WriteLine(x);
count++;
if (count == k)
return;
}
}
}
// Driver Code to test the code.
public static void Main(String[] args)
{
int []arr = {3, 1, 4, 4,
5, 2, 6, 1};
int n = arr.Length;
int k = 2;
print_N_mostFrequentNumber(arr, n, k);
}
}
// This code is contributed by Princi Singh
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.
mp.set(arr[i], mp.get(arr[i])==null?1:mp.get(arr[i]) + 1);
}
// Initialize an array list of array lists
let freq = [];
for (let i = 0; i <= n; i++)
freq.push([]);
// Use frequencies as indexes and add corresponding
// values to the list
for (let [key, value] of mp.entries())
freq[value].push(key);
// Traverse freq[] from right side.
let count = 0;
for (let i = n; i >= 0; i--) {
for (let x=0;x< freq[i].length;x++) {
document.write(freq[i][x]+" ");
count++;
if (count == k)
return;
}
}
}
// Driver Code to test the code.
let arr = [ 3, 1, 4, 4, 5, 2, 6, 1 ];
let n = arr.length;
let k = 2;
print_N_mostFrequentNumber(arr, n, k);
// This code is contributed by patel2127
</script>
Producción:
4 1
Complejidad Temporal: O(n)
Espacio Auxiliar: O(n)
Impresión según primera aparición. Para mantener el orden requerido, recorremos la array original en lugar del mapa. Para evitar duplicados, debemos marcar las entradas procesadas como -1 en el mapa.
C++
// C++ implementation to find k numbers with most
// occurrences in the given array
#include <bits/stdc++.h>
using namespace std;
// 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]]++;
// Use frequencies as indexes and put
// elements with given frequency in a
// vector (related to a frequency)
vector<int> freq[n + 1];
for (int i = 0; i < n; i++) {
int f = um[arr[i]];
if (f != -1) {
freq[f].push_back(arr[i]);
um[arr[i]] = -1;
}
}
// Initialize count of items printed
int count = 0;
// Traverse the frequency array from
// right side as we need the most
// frequent items.
for (int i = n; i >= 0; i--) {
// Print items of current frequency
for (int x : freq[i]) {
cout << x << " ";
count++;
if (count == k)
return;
}
}
}
// 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 = 3;
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);
}
// Initialize an array list of array lists
List<List<Integer> > freq = new ArrayList<List<Integer> >();
for (int i = 0; i <= n; i++)
freq.add(new ArrayList<Integer>());
// Use frequencies as indexes and add corresponding
// values to the list
for (int i = 0; i < n; i++) {
int f = mp.get(arr[i]);
if (f != -1) {
freq.get(f).add(arr[i]);
mp.put(arr[i], -1);
}
}
// Traverse freq[] from right side.
int count = 0;
for (int i = n; i >= 0; i--) {
for (int x : freq.get(i)) {
System.out.println(x);
count++;
if (count == k)
return;
}
}
}
// Driver Code to test the code.
public static void main(String[] args)
{
int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 };
int n = arr.length;
int k = 3;
print_N_mostFrequentNumber(arr, n, k);
}
}
Python3
# Python implementation to find k elements
# with max occurrence.
def print_N_mostFrequentNumber(arr, n, k):
mp = {}
# Put count of all the distinct
# elements in Map with element
# as the key & count as the value.
for i in range(n):
# Get the count for the element
# if already present in the Map
# or get the default value which is 0.
if arr[i] in mp:
mp[arr[i]] += 1
else:
mp[arr[i]] = 0
# Initialize an array list of array lists
freq = [[] for i in range(n+1)]
# Use frequencies as indexes and
# add corresponding values to
# the list
for i in range(n):
f = mp[arr[i]]
if (f != -1):
freq[f].append(arr[i])
mp[arr[i]] = -1
# Traverse []freq from right side.
count = 0
for i in range(n, -1, -1):
for x in freq[i]:
print(x ,end = " ")
count+=1
if (count == k):
return
# Driver Code
arr = [3, 1, 4, 4, 5, 2, 6, 1]
n = len(arr)
k = 3
print_N_mostFrequentNumber(arr, n, k)
# This code is contributed by Shubham Singh
C#
// C# implementation to find k elements
// with max occurrence.
using System;
using System.Collections.Generic;
class GFG{
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]]++;
else
mp.Add(arr[i], 0);
}
// Initialize an array list of array lists
List<List<int>> freq = new List<List<int>>();
for(int i = 0; i <= n; i++)
freq.Add(new List<int>());
// Use frequencies as indexes and
// add corresponding values to
// the list
for(int i = 0; i < n; i++)
{
int f = mp[arr[i]];
if (f != -1)
{
freq[f].Add(arr[i]);
if (mp.ContainsKey(arr[i]))
mp[arr[i]] = -1;
else
mp.Add(arr[i], 0);
}
}
// Traverse []freq from right side.
int count = 0;
for(int i = n; i >= 0; i--)
{
foreach(int x in freq[i])
{
Console.Write(x);
Console.Write(" ");
count++;
if (count == k)
return;
}
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 1, 4, 4, 5, 2, 6, 1 };
int n = arr.Length;
int k = 3;
print_N_mostFrequentNumber(arr, n, k);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript implementation to find k elements
// with max occurrence.
function print_N_mostFrequentNumber(arr, n, k) {
var mp = {};
// Put count of all the distinct
// elements in Map with element
// as the key & count as the value.
for (var 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.hasOwnProperty(arr[i]))
mp[arr[i]]++;
else
mp[arr[i]] = 0;
}
// Initialize an array list of array lists
var freq = Array.from(Array(n + 1), () => Array());
// Use frequencies as indexes and
// add corresponding values to
// the list
for (var i = 0; i < n; i++) {
var f = mp[arr[i]];
if (f !== -1) {
freq[f].push(arr[i]);
if (mp.hasOwnProperty(arr[i]))
mp[arr[i]] = -1;
else
mp[arr[i]] = 0;
}
}
// Traverse []freq from right side.
var count = 0;
for (var i = n; i >= 0; i--) {
for (const x of freq[i]) {
document.write(x + " ");
count++;
if (count === k)
return;
}
}
}
// Driver Code
var arr = [3, 1, 4, 4, 5, 2, 6, 1];
var n = arr.length;
var k = 3;
print_N_mostFrequentNumber(arr, n, k);
</script>
Producción:
1 4 3
Complejidad temporal: O(n)
Espacio auxiliar: O(n)