Dada una array arr que tiene N strings y un número entero K , la tarea es encontrar la K-ésima string distinta lexicográficamente más pequeña . Imprime una string vacía si no existe tal string.
Ejemplo:
Entrada: arr[]={“aa”, “aa”, “bb”, “cc”, “dd”, “cc”}, K = 2
Salida: dd
Explicación: Las distintas strings son: “bb”, “dd ”. La segunda string más pequeña entre estas es «dd»Entrada: arr[]={“aa”, “aa”, “bb”, “cc”, “dd”, “cc”}, K = 1
Salida: bb
Enfoque: el problema dado se puede resolver clasificando primero la array de strings dada y luego imprimiendo la K-ésima string con frecuencia 1. Siga los pasos a continuación para resolver este problema:
- Ordenar la array dada de strings
- Cree un mapa para almacenar la frecuencia de cada string.
- Ahora, recorra el mapa y reduzca el valor de K cada vez que encuentre una string que tenga una frecuencia de uno.
- Cuando K se vuelve cero, imprime la siguiente string que tiene una frecuencia de 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to print lexicographically // smallest Kth string string KthDistinctString(vector<string>& arr, int K) { // Sorting the array of strings sort(arr.begin(), arr.end()); // Map to store the strings map<string, int> mp; for (auto x : arr) { mp[x]++; } for (auto x : mp) { // Reducing K if (x.second == 1) { K--; } if (K == 0 and x.second == 1) { return x.first; } } return ""; } // Driver Code int main() { vector<string> a = { "aa", "aa", "bb", "cc", "dd", "cc" }; int K = 2; cout << KthDistinctString(a, K); }
Java
// Java code for the above approach import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; class GFG { // Function to print lexicographically // smallest Kth string static String KthDistinctString(ArrayList<String> arr, int K) { // Sorting the array of strings Collections.sort(arr); // Map to store the strings HashMap<String, Integer> mp = new HashMap<String, Integer>(); for (String x : arr) { int count = 0; if (mp.containsKey(x)) { count = mp.get(x); } mp.put(x, count + 1); } for (String x : mp.keySet()) { // Reducing K if (mp.get(x) == 1) { K--; } if (K == 0 && mp.get(x) == 1) { return x; } } return ""; } // Driver Code public static void main(String args[]) { ArrayList<String> a = new ArrayList<String>(); a.add("aa"); a.add("aa"); a.add("bb"); a.add("cc"); a.add("dd"); a.add("cc"); int K = 2; System.out.println(KthDistinctString(a, K)); } } // This code is contributed by gfgking
Python3
# Python3 code for the above approach # Function to print lexicographically # smallest Kth string def KthDistinctString(arr, K): # Sorting the array of strings arr.sort() # Map to store the strings mp = {} for x in arr: if x in mp: mp[x] += 1 else: mp[x] = 1 for x in mp: # Reducing K if (mp[x] == 1): K -= 1 if (K == 0 and mp[x] == 1): return x return "" # Driver Code if __name__ == "__main__": a = [ "aa", "aa", "bb", "cc", "dd", "cc" ] K = 2 print(KthDistinctString(a, K)) # This code is contributed by rakeshsahni
C#
// C# code for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to print lexicographically // smallest Kth string static string KthDistinctString(ArrayList arr, int K) { // Sorting the array of strings arr.Sort(); // Map to store the strings Dictionary<string, int> mp = new Dictionary<string, int>(); foreach (string x in arr) { int count = 0; if (mp.ContainsKey(x)) { count = mp[x]; } mp[x] = count + 1; } foreach (KeyValuePair<string, int> x in mp) { // Reducing K if (x.Value == 1) { K--; } if (K == 0 && x.Value == 1) { return x.Key; } } return ""; } // Driver Code public static void Main() { ArrayList a = new ArrayList(); a.Add("aa"); a.Add("aa"); a.Add("bb"); a.Add("cc"); a.Add("dd"); a.Add("cc"); int K = 2; Console.Write(KthDistinctString(a, K)); } } // This code is contributed by Samim Hossain Mondal.
Javascript
<script> // JavaScript Program to implement // the above approach // Function to print lexicographically // smallest Kth string function KthDistinctString(arr, K) { // Sorting the array of strings arr.sort(); // Map to store the strings let mp = new Map(); for (let x of arr) { if (mp.has(x)) mp.set(x, mp.get(x) + 1); else mp.set(x, 1); } for (let [key, value] of mp) { // Reducing K if (value == 1) { K--; } if (K == 0 && value == 1) { return key; } } return ""; } // Driver Code let a = ["aa", "aa", "bb", "cc", "dd", "cc"]; let K = 2; document.write(KthDistinctString(a, K)); // This code is contributed by Potta Lokesh </script>
dd
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por 18bhupenderyadav18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA