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