Dada una array arr[] de N enteros positivos donde los enteros están en el rango de 1 a N , la tarea es verificar si la frecuencia de los elementos en la array es única o no. Si toda la frecuencia es única, imprima «Sí» , de lo contrario, imprima «No» .
Ejemplos:
Entrada: N = 5, arr[] = {1, 1, 2, 5, 5}
Salida: No
Explicación:
La array contiene 2 (1), 1 (2) y 2 (5), ya que el número de frecuencia de 1 y 5 son iguales, es decir, 2 veces. Por lo tanto, esta array no cumple la condición.Entrada: N = 10, arr[] = {2, 2, 5, 10, 1, 2, 10, 5, 10, 2}
Salida: Sí
Explicación:
Número de 1 -> 1
Número de 2 -> 4
Número de 5’s -> 2
Número de 10’s -> 3.
Dado que el número de ocurrencias de los elementos presentes en la array es único. Por lo tanto, esta array no cumple la condición.
Enfoque ingenuo: la idea es verificar cada número del 1 al N si está presente en la array o no. En caso afirmativo, cuente la frecuencia de ese elemento en la array y almacene la frecuencia en una array. Por último, solo verifique si hay algún elemento duplicado en la array e imprima la salida en consecuencia.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque Eficiente: La idea es usar Hashing . A continuación se muestran los pasos:
- Recorra la array dada arr[] y almacene la frecuencia de cada elemento en un Map .
- Ahora recorra el mapa y verifique si el conteo de algún elemento ocurrió más de una vez.
- Si el recuento de cualquier elemento en los pasos anteriores es más de uno, imprima » No» , de lo contrario imprima «Sí» .
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 check whether the // frequency of elements in array // is unique or not. bool checkUniqueFrequency(int arr[], int n) { // Freq map will store the frequency // of each element of the array unordered_map<int, int> freq; // Store the frequency of each // element from the array for (int i = 0; i < n; i++) { freq[arr[i]]++; } unordered_set<int> uniqueFreq; // Check whether frequency of any // two or more elements are same // or not. If yes, return false for (auto& i : freq) { if (uniqueFreq.count(i.second)) return false; else uniqueFreq.insert(i.second); } // Return true if each // frequency is unique return true; } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 1, 2, 5, 5 }; int n = sizeof arr / sizeof arr[0]; // Function Call bool res = checkUniqueFrequency(arr, n); // Print the result if (res) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
Java
// Java code for the above approach import java.util.*; class GFG{ // Function to check whether the // frequency of elements in array // is unique or not. static boolean checkUniqueFrequency(int arr[], int n) { // Freq map will store the frequency // of each element of the array HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); // Store the frequency of each // element from the array for(int i = 0; i < n; i++) { if(freq.containsKey(arr[i])) { freq.put(arr[i], freq.get(arr[i]) + 1); }else { freq.put(arr[i], 1); } } HashSet<Integer> uniqueFreq = new HashSet<Integer>(); // Check whether frequency of any // two or more elements are same // or not. If yes, return false for(Map.Entry<Integer, Integer> i : freq.entrySet()) { if (uniqueFreq.contains(i.getValue())) return false; else uniqueFreq.add(i.getValue()); } // Return true if each // frequency is unique return true; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 1, 1, 2, 5, 5 }; int n = arr.length; // Function call boolean res = checkUniqueFrequency(arr, n); // Print the result if (res) System.out.print("Yes" + "\n"); else System.out.print("No" + "\n"); } } // This code is contributed by PrinciRaj1992
Python3
# Python3 code for # the above approach from collections import defaultdict # Function to check whether the # frequency of elements in array # is unique or not. def checkUniqueFrequency(arr, n): # Freq map will store the frequency # of each element of the array freq = defaultdict (int) # Store the frequency of each # element from the array for i in range (n): freq[arr[i]] += 1 uniqueFreq = set([]) # Check whether frequency of any # two or more elements are same # or not. If yes, return false for i in freq: if (freq[i] in uniqueFreq): return False else: uniqueFreq.add(freq[i]) # Return true if each # frequency is unique return True # Driver Code if __name__ == "__main__": # Given array arr[] arr = [1, 1, 2, 5, 5] n = len(arr) # Function Call res = checkUniqueFrequency(arr, n) # Print the result if (res): print ("Yes") else: print ("No") # This code is contributed by Chitranayal
C#
// C# code for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check whether the // frequency of elements in array // is unique or not. static bool checkUniqueFrequency(int []arr, int n) { // Freq map will store the frequency // of each element of the array Dictionary<int, int> freq = new Dictionary<int, int>(); // Store the frequency of each // element from the array for(int i = 0; i < n; i++) { if(freq.ContainsKey(arr[i])) { freq[arr[i]] = freq[arr[i]] + 1; }else { freq.Add(arr[i], 1); } } HashSet<int> uniqueFreq = new HashSet<int>(); // Check whether frequency of any // two or more elements are same // or not. If yes, return false foreach(KeyValuePair<int, int> i in freq) { if (uniqueFreq.Contains(i.Value)) return false; else uniqueFreq.Add(i.Value); } // Return true if each // frequency is unique return true; } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = { 1, 1, 2, 5, 5 }; int n = arr.Length; // Function call bool res = checkUniqueFrequency(arr, n); // Print the result if (res) Console.Write("Yes" + "\n"); else Console.Write("No" + "\n"); } } // This code is contributed by sapnasingh4991
Javascript
<script> // Javascript code for the above approach // Function to check whether the // frequency of elements in array // is unique or not. function checkUniqueFrequency(arr, n) { // Freq map will store the frequency // of each element of the array let freq = new Map(); // Store the frequency of each // element from the array for(let i = 0; i < n; i++) { if (freq.has(arr[i])) { freq.set(arr[i], freq.get(arr[i]) + 1); } else { freq.set(arr[i], 1); } } let uniqueFreq = new Set(); // Check whether frequency of any // two or more elements are same // or not. If yes, return false for(let [key, value] of freq.entries()) { if (uniqueFreq.has(value)) return false; else uniqueFreq.add(value); } // Return true if each // frequency is unique return true; } // Driver Code // Given array arr[] let arr = [ 1, 1, 2, 5, 5 ]; let n = arr.length; // Function call let res = checkUniqueFrequency(arr, n); // Print the result if (res) document.write("Yes" + "<br>"); else document.write("No" + "<br>"); // This code is contributed by avanitrachhadiya2155 </script>
No
Complejidad temporal: O(N), donde N es el número de elementos de la array.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por equbalzeeshan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA