Encuentre los k números principales (o los más frecuentes) en una secuencia

Dada una array de n números. Su tarea es leer números de la array y mantener como máximo K números en la parte superior (de acuerdo con su frecuencia decreciente) cada vez que se lee un nuevo número. Básicamente, necesitamos imprimir los k números principales ordenados por frecuencia cuando el flujo de entrada ha incluido k elementos distintos; de lo contrario, debemos imprimir todos los elementos distintos ordenados por frecuencia.

Ejemplos: 

Entrada: arr[] = {5, 2, 1, 3, 2} 
k = 4 
Salida: 5 2 5 1 2 5 1 2 3 5 2 1 3 5 

Explicación: 

1. Después de leer 5, solo hay un elemento 5 cuya frecuencia es máxima hasta ahora. 
   así que imprime 5.
2. Después de la lectura 2, tendremos dos elementos 2 y 5 con la misma frecuencia. 
   Como 2, es menor que 5 pero su frecuencia es la misma, imprimiremos 2 5.
3. Después de leer 1, tendremos 3 elementos 1, 2 y 5 con la misma frecuencia, 
   así que imprime 1 2 5.
4. Del mismo modo, después de leer 3, imprime 1 2 3 5
5. Después de leer el último elemento 2, ya que 2 ya ocurrió, ahora tenemos una 
   frecuencia de 2 como 2. Entonces mantenemos 2 en la parte superior y luego el resto del elemento 
   con la misma frecuencia en orden ordenado. Así que imprime, 2 1 3 5.

Entrada: arr[] = {5, 2, 1, 3, 4} 
k = 4 
Salida: 5 2 5 1 2 5 1 2 3 5 1 2 3 4 

Explicación:

1. Después de leer 5, solo hay un elemento 5 cuya frecuencia es máxima hasta ahora. 
   así que imprime 5.
2. Después de la lectura 2, tendremos dos elementos 2 y 5 con la misma frecuencia. 
   Como 2, es menor que 5 pero su frecuencia es la misma, imprimiremos 2 5.
3. Después de leer 1, tendremos 3 elementos 1, 2 y 5 con la misma frecuencia, 
   así que imprima 1 2 5. 
   De manera similar, después de leer 3, imprima 1 2 3 5
4. Después de leer el último elemento 4, todos los elementos tienen la misma frecuencia 
   Así que imprime, 1 2 3 4

Enfoque: La idea es almacenar los k elementos superiores con la máxima frecuencia. Para almacenarlos se puede usar un vector o una array. Para realizar un seguimiento de las frecuencias de los elementos, se crea un HashMap para almacenar pares de elementos y frecuencias. Dada una secuencia de números, cuando aparece un nuevo elemento en la secuencia, actualice la frecuencia de ese elemento en HashMap y coloque ese elemento al final de la lista de K números (elementos k + 1 totales), ahora compare los elementos adyacentes de la lista y intercambiar si el elemento de mayor frecuencia se almacena junto a él.

Algoritmo: 

1. Cree un Hashmap hm y una array de k + 1 de longitud.
2. Atraviesa la array de entrada de principio a fin.
3. Inserte el elemento en la posición k+1 de la array, actualice la frecuencia de ese elemento en HashMap.
4. Ahora, recorra la array temporal de principio a fin: 1
5. Para cada elemento, compare la frecuencia e intercambie si el elemento de mayor frecuencia está almacenado junto a él, si la frecuencia es la misma, entonces el intercambio es el siguiente elemento mayor.
6. imprima el elemento k superior en cada recorrido de la array original.

Implementación: 

// C++ program to find top k elements in a stream
#include <bits/stdc++.h>
using namespace std;
 
// Function to print top k numbers
void kTop(int a[], int n, int k)
{
    // vector of size k+1 to store elements
    vector<int> top(k + 1);
 
    // array to keep track of frequency
    unordered_map<int, int> freq;
 
    // iterate till the end of stream
    for (int m = 0; m < n; m++) {
        // increase the frequency
        freq[a[m]]++;
 
        // store that element in top vector
        top[k] = a[m];
 
        // search in top vector for same element
        auto it = find(top.begin(), top.end() - 1, a[m]);
 
        // iterate from the position of element to zero
        for (int i = distance(top.begin(), it) - 1; i >= 0; --i) {
            // compare the frequency and swap if higher
            // frequency element is stored next to it
            if (freq[top[i]] < freq[top[i + 1]])
                swap(top[i], top[i + 1]);
 
            // if frequency is same compare the elements
            // and swap if next element is high
            else if ((freq[top[i]] == freq[top[i + 1]])
                     && (top[i] > top[i + 1]))
                swap(top[i], top[i + 1]);
            else
                break;
        }
 
        // print top k elements
        for (int i = 0; i < k && top[i] != 0; ++i)
            cout << top[i] << ' ';
    }
    cout << endl;
}
 
// Driver program to test above function
int main()
{
    int k = 4;
    int arr[] = { 5, 2, 1, 3, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    kTop(arr, n, k);
    return 0;
}

import java.io.*;
import java.util.*;
class GFG {
 
    // function to search in top vector for element
    static int find(int[] arr, int ele)
    {
        for (int i = 0; i < arr.length; i++)
            if (arr[i] == ele)
                return i;
        return -1;
    }
 
    // Function to print top k numbers
    static void kTop(int[] a, int n, int k)
    {
        // vector of size k+1 to store elements
        int[] top = new int[k + 1];
 
        // array to keep track of frequency
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i < k + 1; i++)
            freq.put(i, 0);
 
        // iterate till the end of stream
        for (int m = 0; m < n; m++) {
            // increase the frequency
            if (freq.containsKey(a[m]))
                freq.put(a[m], freq.get(a[m]) + 1);
            else
                freq.put(a[m], 1);
 
            // store that element in top vector
            top[k] = a[m];
 
            // search in top vector for same element
            int i = find(top, a[m]);
            i -= 1;
 
            // iterate from the position of element to zero
            while (i >= 0) {
                // compare the frequency and swap if higher
                // frequency element is stored next to it
                if (freq.get(top[i]) < freq.get(top[i + 1])) {
                    int temp = top[i];
                    top[i] = top[i + 1];
                    top[i + 1] = temp;
                }
 
                // if frequency is same compare the elements
                // and swap if next element is high
                else if ((freq.get(top[i]) == freq.get(top[i + 1])) && (top[i] > top[i + 1])) {
                    int temp = top[i];
                    top[i] = top[i + 1];
                    top[i + 1] = temp;
                }
 
                else
                    break;
                i -= 1;
            }
 
            // print top k elements
            for (int j = 0; j < k && top[j] != 0; ++j)
                System.out.print(top[j] + " ");
        }
        System.out.println();
    }
 
    // Driver program to test above function
    public static void main(String args[])
    {
        int k = 4;
        int[] arr = { 5, 2, 1, 3, 2 };
        int n = arr.length;
        kTop(arr, n, k);
    }
}
 
// This code is contributed by rachana soma

# Python program to find top k elements in a stream
 
# Function to print top k numbers
def kTop(a, n, k):
 
    # list of size k + 1 to store elements
    top = [0 for i in range(k + 1)]
  
    # dictionary to keep track of frequency
    freq = {i:0 for i in range(k + 1)}
 
    # iterate till the end of stream
    for m in range(n):
 
        # increase the frequency
        if a[m] in freq.keys():
            freq[a[m]] += 1
        else:
            freq[a[m]] = 1
 
        # store that element in top vector
        top[k] = a[m]
  
        i = top.index(a[m])
        i -= 1
         
        while i >= 0:
 
            # compare the frequency and swap if higher
            # frequency element is stored next to it
            if (freq[top[i]] < freq[top[i + 1]]):
                t = top[i]
                top[i] = top[i + 1]
                top[i + 1] = t
             
            # if frequency is same compare the elements
            # and swap if next element is high
            else if ((freq[top[i]] == freq[top[i + 1]]) and (top[i] > top[i + 1])):
                t = top[i]
                top[i] = top[i + 1]
                top[i + 1] = t
            else:
                break
            i -= 1
         
        # print top k elements
        i = 0
        while i < k and top[i] != 0:
            print(top[i],end=" ")
            i += 1
    print()
  
# Driver program to test above function
k = 4
arr = [ 5, 2, 1, 3, 2 ]
n = len(arr)
kTop(arr, n, k)
 
# This code is contributed by Sachin Bisht

// C# program to find top k elements in a stream
using System;
using System.Collections.Generic;
 
class GFG {
    // function to search in top vector for element
    static int find(int[] arr, int ele)
    {
        for (int i = 0; i < arr.Length; i++)
            if (arr[i] == ele)
                return i;
        return -1;
    }
 
    // Function to print top k numbers
    static void kTop(int[] a, int n, int k)
    {
        // vector of size k+1 to store elements
        int[] top = new int[k + 1];
 
        // array to keep track of frequency
        Dictionary<int,
                   int>
            freq = new Dictionary<int,
                                  int>();
        for (int i = 0; i < k + 1; i++)
            freq.Add(i, 0);
 
        // iterate till the end of stream
        for (int m = 0; m < n; m++) {
            // increase the frequency
            if (freq.ContainsKey(a[m]))
                freq[a[m]]++;
            else
                freq.Add(a[m], 1);
 
            // store that element in top vector
            top[k] = a[m];
 
            // search in top vector for same element
            int i = find(top, a[m]);
            i--;
 
            // iterate from the position of element to zero
            while (i >= 0) {
                // compare the frequency and swap if higher
                // frequency element is stored next to it
                if (freq[top[i]] < freq[top[i + 1]]) {
                    int temp = top[i];
                    top[i] = top[i + 1];
                    top[i + 1] = temp;
                }
 
                // if frequency is same compare the elements
                // and swap if next element is high
                else if (freq[top[i]] == freq[top[i + 1]] && top[i] > top[i + 1]) {
                    int temp = top[i];
                    top[i] = top[i + 1];
                    top[i + 1] = temp;
                }
                else
                    break;
 
                i--;
            }
 
            // print top k elements
            for (int j = 0; j < k && top[j] != 0; ++j)
                Console.Write(top[j] + " ");
        }
        Console.WriteLine();
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int k = 4;
        int[] arr = { 5, 2, 1, 3, 2 };
        int n = arr.Length;
        kTop(arr, n, k);
    }
}
 
// This code is contributed by
// sanjeev2552

<script>
 
      // JavaScript program to find top k elements in a stream
      // function to search in top vector for element
      function find(arr, ele) {
        for (var i = 0; i < arr.length; i++)
        if (arr[i] === ele) return i;
        return -1;
      }
 
      // Function to print top k numbers
      function kTop(a, n, k) {
        // vector of size k+1 to store elements
        var top = new Array(k + 1).fill(0);
 
        // array to keep track of frequency
 
        var freq = {};
        for (var i = 0; i < k + 1; i++) freq[i] = 0;
 
        // iterate till the end of stream
        for (var m = 0; m < n; m++) {
          // increase the frequency
          if (freq.hasOwnProperty(a[m])) freq[a[m]]++;
          else freq[a[m]] = 1;
 
          // store that element in top vector
          top[k] = a[m];
 
          // search in top vector for same element
          var i = find(top, a[m]);
          i--;
 
          // iterate from the position of element to zero
          while (i >= 0) {
            // compare the frequency and swap if higher
            // frequency element is stored next to it
            if (freq[top[i]] < freq[top[i + 1]]) {
              var temp = top[i];
              top[i] = top[i + 1];
              top[i + 1] = temp;
            }
 
            // if frequency is same compare the elements
            // and swap if next element is high
            else if (freq[top[i]] === freq[top[i + 1]] &&
            top[i] > top[i + 1])
            {
              var temp = top[i];
              top[i] = top[i + 1];
              top[i + 1] = temp;
            } else break;
 
            i--;
          }
 
          // print top k elements
          for (var j = 0; j < k && top[j] !== 0; ++j)
            document.write(top[j] + " ");
        }
        document.write("<br>");
      }
 
      // Driver Code
      var k = 4;
      var arr = [5, 2, 1, 3, 2];
      var n = arr.length;
      kTop(arr, n, k);
       
</script>

5 2 5 1 2 5 1 2 3 5 2 1 3 5

Análisis de Complejidad: 

• Complejidad temporal: O( n * k ). 
  En cada recorrido, se recorre la array temporal de tamaño k, por lo que la complejidad del tiempo es O (n * k).
• Complejidad espacial: O(n). 
  Para almacenar los elementos en HashMap O(n) se requiere espacio.

Este artículo es una contribución de Niteesh Kumar . 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 contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.