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:
- 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.
- 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.
- Las strings con frecuencias iguales se priorizan alfabéticamente, es decir, la string alfabéticamente mayor tiene mayor prioridad .
- 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.
- 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>
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