Dada una array arr , la tarea es imprimir los elementos de la array en orden descendente junto con sus frecuencias.
Ejemplos:
Entrada: arr[] = {1, 3, 3, 3, 4, 4, 5}
Salida: 5 ocurren 1 vez
4 ocurren 2 veces
3 ocurren 3 veces
1 ocurre 1 vez
Entrada: arr[] = {1, 1, 1, 2, 3, 4, 9, 9, 10}
Salida: 10 ocurre 1 vez
9 ocurre 2 veces
4 ocurre 1 vez
3 ocurre 1 vez
2 ocurre 1 vez
1 ocurre 3 veces
Enfoque ingenuo: use alguna estructura de datos (por ejemplo, multiconjunto ) que almacene elementos en orden decreciente y luego imprima los elementos uno por uno con su recuento y luego bórrelos de la estructura de datos. La complejidad temporal será O(N log N) y el espacio auxiliar será O(N) para la estructura de datos utilizada.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to print the elements in
// descending along with their frequencies
#include <bits/stdc++.h>
using namespace std;
// Function to print the elements in descending
// along with their frequencies
void printElements(int a[], int n)
{
// A multiset to store elements in decreasing order
multiset<int, greater<int> > ms;
// Insert elements in the multiset
for (int i = 0; i < n; i++) {
ms.insert(a[i]);
}
// Print the elements along with their frequencies
while (!ms.empty()) {
// Find the maximum element
int maxel = *ms.begin();
// Number of times it occurs
int times = ms.count(maxel);
cout << maxel << " occurs " << times << " times\n";
// Erase the maxel
ms.erase(maxel);
}
}
// Driver Code
int main()
{
int a[] = { 1, 1, 1, 2, 3, 4, 9, 9, 10 };
int n = sizeof(a) / sizeof(a[0]);
printElements(a, n);
return 0;
}
Producción:
10 occurs 1 times 9 occurs 2 times 4 occurs 1 times 3 occurs 1 times 2 occurs 1 times 1 occurs 3 times
Complejidad de tiempo: O(N*logN), ya que estamos usando un bucle para recorrer N veces y en cada recorrido, estamos realizando una operación de conjuntos múltiples que nos costará logN tiempo.
Espacio auxiliar: O(N), ya que estamos usando espacio extra para el conjunto múltiple.
Enfoque eficiente: ordene la array en orden descendente y luego comience a imprimir los elementos desde el principio junto con sus frecuencias.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print the elements in
// descending along with their frequencies
#include <bits/stdc++.h>
using namespace std;
// Function to print the elements in descending
// along with their frequencies
void printElements(int a[], int n)
{
// Sorts the element in decreasing order
sort(a, a + n, greater<int>());
int cnt = 1;
// traverse the array elements
for (int i = 0; i < n - 1; i++) {
// Prints the number and count
if (a[i] != a[i + 1]) {
cout << a[i] << " occurs " << cnt << " times\n";
cnt = 1;
}
else
cnt += 1;
}
// Prints the last step
cout << a[n - 1] << " occurs " << cnt << " times\n";
}
// Driver Code
int main()
{
int a[] = { 1, 1, 1, 2, 3, 4, 9, 9, 10 };
int n = sizeof(a) / sizeof(a[0]);
printElements(a, n);
return 0;
}
Java
// Java program to print the elements in
// descending along with their frequencies
import java.util.*;
class GFG
{
// Function to print the elements in descending
// along with their frequencies
static void printElements(int a[], int n)
{
// Sorts the element in decreasing order
Arrays.sort(a);
a = reverse(a);
int cnt = 1;
// traverse the array elements
for (int i = 0; i < n - 1; i++)
{
// Prints the number and count
if (a[i] != a[i + 1])
{
System.out.print(a[i]+ " occurs " +
cnt + " times\n");
cnt = 1;
}
else
cnt += 1;
}
// Prints the last step
System.out.print(a[n - 1]+ " occurs " +
cnt + " times\n");
}
static int[] reverse(int a[])
{
int i, n = a.length, t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 1, 1, 2, 3, 4, 9, 9, 10 };
int n = a.length;
printElements(a, n);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to print the elements in # descending along with their frequencies # Function to print the elements in # descending along with their frequencies def printElements(a, n) : # Sorts the element in decreasing order a.sort(reverse = True) cnt = 1 # traverse the array elements for i in range(n - 1) : # Prints the number and count if (a[i] != a[i + 1]) : print(a[i], " occurs ", cnt, "times") cnt = 1 else : cnt += 1 # Prints the last step print(a[n - 1], "occurs", cnt, "times") # Driver Code if __name__ == "__main__" : a = [ 1, 1, 1, 2, 3, 4, 9, 9, 10 ] n = len(a) printElements(a, n) # This code is contributed by Ryuga
C#
// C# program to print the elements in
// descending along with their frequencies
using System;
class GFG
{
// Function to print the elements in descending
// along with their frequencies
static void printElements(int []a, int n)
{
// Sorts the element in decreasing order
Array.Sort(a);
a = reverse(a);
int cnt = 1;
// traverse the array elements
for (int i = 0; i < n - 1; i++)
{
// Prints the number and count
if (a[i] != a[i + 1])
{
Console.Write(a[i]+ " occurs " +
cnt + " times\n");
cnt = 1;
}
else
cnt += 1;
}
// Prints the last step
Console.Write(a[n - 1]+ " occurs " +
cnt + " times\n");
}
static int[] reverse(int []a)
{
int i, n = a.Length, t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 1, 1, 1, 2, 3, 4, 9, 9, 10 };
int n = a.Length;
printElements(a, n);
}
}
// This code is contributed by PrinciRaj1992
PHP
<?php
// PHP program to print the elements in
// descending along with their frequencies
// Function to print the elements in
// descending along with their frequencies
function printElements(&$a, $n)
{
// Sorts the element in
// decreasing order
rsort($a);
$cnt = 1;
// traverse the array elements
for ($i = 0; $i < $n - 1; $i++)
{
// Prints the number and count
if ($a[$i] != $a[$i + 1])
{
echo ($a[$i]);
echo (" occurs " );
echo $cnt ;
echo (" times\n");
$cnt = 1;
}
else
$cnt += 1;
}
// Prints the last step
echo ($a[$n - 1]);
echo (" occurs ");
echo $cnt;
echo (" times\n");
}
// Driver Code
$a = array(1, 1, 1, 2, 3,
4, 9, 9, 10 );
$n = sizeof($a);
printElements($a, $n);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// javascript program to print the elements in
// descending along with their frequencies
// Function to print the elements in descending
// along with their frequencies
function printElements(a, n)
{
// Sorts the element in decreasing order
a=a.sort(compare);
a = reverse(a);
var cnt = 1;
// traverse the array elements
for (var i = 0; i < n - 1; i++)
{
// Prints the number and count
if (a[i] != a[i + 1])
{
document.write(a[i]+ " occurs " + cnt + " times" + "<br>");
cnt = 1;
}
else
cnt += 1;
}
// Prints the last step
document.write(a[n - 1]+ " occurs " + cnt + " times" + "<br>");
}
function reverse(a){
var i, n = a.length, t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
function compare(a, b) {
if (a < b) {
return -1;
} else if (a > b) {
return 1;
} else {
return 0;
}
}
// Driver Code
var a = [ 1, 1, 1, 2, 3, 4, 9, 9, 10 ];
var n = a.length;
printElements(a, n);
// This code is contributed by bunnyram19.
</script>
Producción:
10 occurs 1 times 9 occurs 2 times 4 occurs 1 times 3 occurs 1 times 2 occurs 1 times 1 occurs 3 times
Complejidad de tiempo: O(N*logN), ya que estamos usando la función de clasificación que nos costará O(N*logN) de tiempo.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.