K strings más frecuentes

Dada una array arr[] de N strings y un entero K , la tarea es imprimir K strings que ocurrieron la mayor cantidad de veces en arr[] . Si dos o más strings tienen la misma frecuencia, imprima la string lexicográficamente más pequeña .
Nota: El valor de K siempre es menor o igual que el número de elementos distintos en la array.

Ejemplos: 

Entrada: str[] = {“geeks”, “geeksforgeeks”, “geeks”, “article”}, K = 1 
Salida: “geeks” 
Explicación: 
“geeks” -> 2 
“geeksforgeeks” -> 1 
“article” – > 1 
Por lo tanto, la string que más aparece es “geeks”

Entrada: str[] = {“coche”, “autobús”, “coche”, “bicicleta”, “coche”, “autobús”, “bicicleta”, “ciclo”}, K = 2 
Salida: “coche”, “ bus” 
Explicación: 
“coche” -> 3 
“autobús” -> 2 
“bicicleta” -> 2 
“ciclo” -> 1 
string “auto” tiene la frecuencia más alta, la string “autobús” y “bicicleta” tienen la segunda frecuencia más alta, pero la string «bus» es lexicográficamente pequeña porque tiene una longitud más corta.

 

Acercarse:

  1. Cuente la frecuencia de cada string en la array y guárdela en un HashMap donde la string es la clave y la frecuencia el valor.
  2. Ahora, clasifique estas claves de acuerdo con sus frecuencias en orden ascendente , esto se hace para mantener las claves con las frecuencias más bajas en la parte superior.
  3. Las strings con frecuencias iguales se priorizan alfabéticamente, es decir, la string alfabéticamente mayor tiene mayor prioridad .
  4. Elimine los principales pares clave-valor N – K del HashMap. Al hacer esto, el contenedor queda con las teclas K con las frecuencias más altas, en orden inverso.
  5. Imprime las strings almacenadas en HashMap.

A continuación se muestra la implementación del enfoque anterior:
 

Java

// Java program for the above approach
import java.util.*;
 
class FrequentWords {
 
    // Function that returns list of K
    // most frequent strings
    public static ArrayList<String>
    frequentWords(ArrayList<String> arr, int K)
    {
 
        // Hash map to store the frequency
        // of each string
        HashMap<String, Integer> Freq
            = new HashMap<>();
 
        // Set the default frequency of
        // each string 0
        for (String word : arr) {
            Freq.put(word,
                     Freq.getOrDefault(word, 0)
                         + 1);
        }
 
        // Using a priority queue to store
        // the strings in accordance of the
        // frequency and alphabetical order
        // (if frequency is equal)
 
        // Lambda expression is used set the
        // priority, if frequencies are not
        // equal than the string with greater
        // frequency is returned else the
        // string which is lexically smaller
        // is returned
        PriorityQueue<String> Order
            = new PriorityQueue<>(
                (a, b)
                    -> (Freq.get(a) != Freq.get(b))
                           ? Freq.get(a) - Freq.get(b)
                           : b.compareTo(a));
 
        // Traverse the HashMap
        for (String word : Freq.keySet()) {
            Order.offer(word);
 
            // Remove top (N - K) elements
            if (Order.size() > K) {
                Order.poll();
            }
        }
 
        // Order queue has K most frequent
        // strings in a reverse order
        ArrayList<String> ans
            = new ArrayList<>();
 
        while (!Order.isEmpty()) {
            ans.add(Order.poll());
        }
 
        // Reverse the ArrayList so as
        // to get in the desired order
        Collections.reverse(ans);
 
        return ans;
    }
 
    // Driver Code
    public static void
        main(String[] args)
    {
        int N = 3, K = 2;
 
        // Given array
        ArrayList<String> arr
            = new ArrayList<String>();
        arr.add("car");
        arr.add("bus");
        arr.add("car");
 
        // Function Call
        ArrayList<String> ans
            = frequentWords(arr, K);
 
        // Print the K most occurring strings
        for (String word : ans) {
            System.out.println(word + " ");
        }
    }
}

Javascript

<script>
 
// Javascript program for the above approach
 
// Function that returns list of K
// most frequent strings
function frequentWords(arr, K)
{
    // Hash map to store the frequency
    // of each string
    var Freq = new Map();
     
    // Set the default frequency of
    // each string 0
    for (var word of arr) {
        Freq.set(word, Freq.has(word)?Freq.get(word):0);
    }
     
    // Using a priority queue to store
    // the strings in accordance of the
    // frequency and alphabetical order
    // (if frequency is equal)
    // Lambda expression is used set the
    // priority, if frequencies are not
    // equal than the string with greater
    // frequency is returned else the
    // string which is lexically smaller
    // is returned
    var Order = [];
 
    // Traverse the HashMap
    for (var word of [...Freq.keys()]) {
        Order.push(word);
        // Remove top (N - K) elements
        if (Order.length > K) {
            Order.pop();
        }
    }
    // Order queue has K most frequent
    // strings in a reverse order
    var ans = [];
    Order.sort((a,b)=>a[0]-b[0]);
    while (Order.length!=0) {
        ans.push(Order[Order.length-1])
        Order.pop();
    }
    // Reverse the ArrayList so as
    // to get in the desired order
    ans.reverse();
    return ans;
}
 
// Driver Code
var N = 3, K = 2;
 
// Given array
var arr = [];
arr.push("car");
arr.push("bus");
arr.push("car");
// Function Call
 
var ans = frequentWords(arr, K);
 
// Print the K most occurring strings
for (var word of ans) {
    document.write(word + "<br>");
}
 
// This code is contributed by noob2000.
</script>
Producción: 

car 
bus

 

Complejidad de tiempo: O(N*log 2 N)
Espacio auxiliar: O(N) 

Publicación traducida automáticamente

Artículo escrito por anurag_sachdeva y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *