Dada una array arr[] de N enteros. La tarea es ordenar la array arr[] según la frecuencia de los elementos en orden decreciente.
Nota: si las frecuencias de los dos elementos son iguales, entonces el elemento más pequeño debe ir primero.
Ejemplos:
Entrada: arr[] = { 4, 4, 5, 6, 4, 2, 2, 8, 5 }
Salida: 4 4 4 2 2 5 5 6 8Entrada: arr[] = { 9, 9, 5, 8, 5 }
Salida: 5 5 9 9 8
Acercarse:
- Almacene la frecuencia de todos los elementos en el arreglo arr[] .
- Para arr[] = { 4, 4, 5, 6, 4, 2, 2, 8, 5 }
La array de frecuencias de la array anterior es:
freq[] = { 0, 0, 2, 0, 3, 2, 0, 1, 0, 1} - Recorra la array de frecuencias y para todos los elementos que tengan una frecuencia mayor que 1 , actualice el valor en la array arr[] como:
frecuencia[2] = 2
arr[0] = 100000*frec[2] + (100000 – 2) = 299998
frec[4] = 3
arr[1] = 100000*frec[2] + (100000 – 4) = 399996
frecuencia[5] = 2
arr[2] = 100000*frec[2] + (100000 – 5) = 299995
frec[6] = 2
arr[3] = 100000*frec[2] + (100000 – 6) = 199994
freq[8] = 2
arr[4] = 100000*freq[2] + (100000 – 2) = 199994
Ahora la array se convierte en:
arr[] = {299998, 399996, 299995, 199994, 199992, 2, 2, 8, 5}
- Ordene la array arr[] en orden decreciente.
- Recorra la array arr[] y para obtener el elemento y la frecuencia de ese elemento según la actualización del elemento de la array en el paso 2, haga lo siguiente:
Para obtener la frecuencia del elemento actual:
frecuencia = arr[i]/100000;
Para obtener el valor:
valor = 100000 – arr[i]%100000
Por ejemplo:
if arr[i] = 399996
frecuencia = arr[i]/100000 = 399996/100000 = 3
valor = 100000 – arr[i]%100000 = 100000 – 99996 = 4
El elemento 4 tiene frecuencia 3 .
- Para cada elemento en arr[] encuentre el valor y la frecuencia (digamos f ) en cada índice e imprima el valor f varias veces.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to sort an array in
// decreasing order of their frequency
#include "bits/stdc++.h"
using namespace std;
// Function that return the index
// upto all the array elements are
// updated.
int sortByFreq(int* arr, int n)
{
// Initialise maxE = -1
int maxE = -1;
// Find the maximum element of
// arr[]
for (int i = 0; i < n; i++) {
maxE = max(maxE, arr[i]);
}
// Create frequency array freq[]
int freq[maxE + 1] = { 0 };
// Update the frequency array as
// per the occurrence of element in
// arr[]
for (int i = 0; i < n; i++) {
freq[arr[i]]++;
}
// Initialise cnt to 0
int cnt = 0;
// Traversing freq[]
for (int i = 0; i <= maxE; i++) {
// If freq of an element is
// greater than 0 update the
// value of arr[] at index cnt
// & increment cnt
if (freq[i] > 0) {
int value = 100000 - i;
arr[cnt] = 100000 * freq[i] + value;
cnt++;
}
}
// Return cnt
return cnt;
}
// Function that print array arr[]
// elements in sorted order
void printSortedArray(int* arr, int cnt)
{
// Traversing arr[] till index cnt
for (int i = 0; i < cnt; i++) {
// Find frequency of elements
int frequency = arr[i] / 100000;
// Find value at index i
int value = 100000 - (arr[i] % 100000);
// Traversing till frequency
// to print value at index i
for (int j = 0; j < frequency; j++) {
cout << value << ' ';
}
}
}
// Driver code
int main()
{
int arr[] = { 4, 4, 5, 6, 4, 2, 2, 8, 5 };
// Size of array arr[]
int n = sizeof(arr) / sizeof(arr[0]);
// Function call to get cnt
int cnt = sortByFreq(arr, n);
// Sort the arr[] in decreasing order
sort(arr, arr + cnt, greater<int>());
// Function that prints elements
// in decreasing order
printSortedArray(arr, cnt);
return 0;
}
Java
// Java program to sort an array in
// decreasing order of their frequency
import java.util.*;
class GFG{
// Function that return the index
// upto all the array elements are
// updated.
static int sortByFreq(Integer []arr, int n)
{
// Initialise maxE = -1
int maxE = -1;
// Find the maximum element of
// arr[]
for (int i = 0; i < n; i++) {
maxE = Math.max(maxE, arr[i]);
}
// Create frequency array freq[]
int freq[] = new int[maxE + 1];
// Update the frequency array as
// per the occurrence of element in
// arr[]
for (int i = 0; i < n; i++) {
freq[arr[i]]++;
}
// Initialise cnt to 0
int cnt = 0;
// Traversing freq[]
for (int i = 0; i <= maxE; i++) {
// If freq of an element is
// greater than 0 update the
// value of arr[] at index cnt
// & increment cnt
if (freq[i] > 0) {
int value = 100000 - i;
arr[cnt] = 100000 * freq[i] + value;
cnt++;
}
}
// Return cnt
return cnt;
}
// Function that print array arr[]
// elements in sorted order
static void printSortedArray(Integer []arr, int cnt)
{
// Traversing arr[] till index cnt
for (int i = 0; i < cnt; i++) {
// Find frequency of elements
int frequency = arr[i] / 100000;
// Find value at index i
int value = 100000 - (arr[i] % 100000);
// Traversing till frequency
// to print value at index i
for (int j = 0; j < frequency; j++) {
System.out.print(value + " ");
}
}
}
// Driver code
public static void main(String[] args)
{
Integer arr[] = { 4, 4, 5, 6, 4, 2, 2, 8, 5 };
// Size of array arr[]
int n = arr.length;
// Function call to get cnt
int cnt = sortByFreq(arr, n);
// Sort the arr[] in decreasing order
Arrays.sort(arr, Collections.reverseOrder());
// Function that prints elements
// in decreasing order
printSortedArray(arr, cnt);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python program to sort an array in # decreasing order of their frequency # Function that return the index # upto all the array elements are # updated. def sortByFreq(arr, n): # Initialise maxE = -1 maxE = -1; # Find the maximum element of # arr[] for i in range(n): maxE = max(maxE, arr[i]) # Create frequency array freq[] freq = [0]*(maxE + 1); # Update the frequency array as # per the occurrence of element in # arr[] for i in range(n): freq[arr[i]] += 1; # Initialise cnt to 0 cnt = 0; # Traversing freq[] for i in range(maxE+1): # If freq of an element is # greater than 0 update the # value of arr[] at index cnt # & increment cnt if (freq[i] > 0): value = 100000 - i; arr[cnt] = 100000 * freq[i] + value; cnt += 1; # Return cnt return cnt; # Function that print array arr[] # elements in sorted order def printSortedArray(arr, cnt): # Traversing arr[] till index cnt for i in range(cnt): # Find frequency of elements frequency = arr[i] / 100000; # Find value at index i value = 100000 - (arr[i] % 100000); # Traversing till frequency # to print value at index i for j in range(int(frequency)): print(value, end=" ") # Driver code if __name__=='__main__': arr = [ 4, 4, 5, 6, 4, 2, 2, 8, 5 ] # Size of array arr[] n = len(arr) # Function call to get cnt cnt = sortByFreq(arr, n); # Sort the arr[] in decreasing order arr.sort(reverse = True) # Function that prints elements # in decreasing order printSortedArray(arr, cnt); # This code is contributed by Princi Singh
C#
// C# program to sort an array in
// decreasing order of their frequency
using System;
class GFG {
// Function that return the index
// upto all the array elements are
// updated.
static int sortByFreq(int[] arr, int n)
{
// Initialise maxE = -1
int maxE = -1;
// Find the maximum element of
// arr[]
for (int i = 0; i < n; i++)
{
maxE = Math.Max(maxE, arr[i]);
}
// Create frequency array freq[]
int[] freq = new int[maxE + 1];
// Update the frequency array as
// per the occurrence of element in
// arr[]
for (int i = 0; i < n; i++)
{
freq[arr[i]]++;
}
// Initialise cnt to 0
int cnt = 0;
// Traversing freq[]
for (int i = 0; i <= maxE; i++)
{
// If freq of an element is
// greater than 0 update the
// value of arr[] at index cnt
// & increment cnt
if (freq[i] > 0)
{
int value = 100000 - i;
arr[cnt] = 100000 * freq[i] + value;
cnt++;
}
}
// Return cnt
return cnt;
}
// Function that print array arr[]
// elements in sorted order
static void printSortedArray(int[] arr, int cnt)
{
// Traversing arr[] till index cnt
for (int i = 0; i < cnt; i++)
{
// Find frequency of elements
int frequency = arr[i] / 100000;
// Find value at index i
int value = 100000 - (arr[i] % 100000);
// Traversing till frequency
// to print value at index i
for (int j = 0; j < frequency; j++)
{
Console.Write(value + " ");
}
}
}
// Driver code
public static void Main()
{
int[] arr = { 4, 4, 5, 6, 4, 2, 2, 8, 5 };
// Size of array arr[]
int n = arr.Length;
// Function call to get cnt
int cnt = sortByFreq(arr, n);
// Sort the arr[] in decreasing order
Array.Sort(arr);
Array.Reverse(arr);
// Function that prints elements
// in decreasing order
printSortedArray(arr, cnt);
}
}
// This code is contributed by subhamahato348
Javascript
<script>
// JavaScript program to sort an array in
// decreasing order of their frequency
// Function that return the index
// upto all the array elements are
// updated.
function sortByFreq(arr, n) {
// Initialise maxE = -1
var maxE = -1;
// Find the maximum element of
// arr[]
for (var i = 0; i < n; i++) {
maxE = Math.max(maxE, arr[i]);
}
// Create frequency array freq[]
var freq = new Array(maxE + 1).fill(0);
// Update the frequency array as
// per the occurrence of element in
// arr[]
for (var i = 0; i < n; i++) {
freq[arr[i]]++;
}
// Initialise cnt to 0
var cnt = 0;
// Traversing freq[]
for (var i = 0; i <= maxE; i++) {
// If freq of an element is
// greater than 0 update the
// value of arr[] at index cnt
// & increment cnt
if (freq[i] > 0) {
var value = 100000 - i;
arr[cnt] = 100000 * freq[i] + value;
cnt++;
}
}
// Return cnt
return cnt;
}
// Function that print array arr[]
// elements in sorted order
function printSortedArray(arr, cnt) {
// Traversing arr[] till index cnt
for (var i = 0; i < cnt; i++) {
// Find frequency of elements
var frequency = parseInt(arr[i] / 100000);
// Find value at index i
var value = 100000 - (arr[i] % 100000);
// Traversing till frequency
// to print value at index i
for (var j = 0; j < frequency; j++) {
document.write(value + " ");
}
}
}
// Driver code
var arr = [4, 4, 5, 6, 4, 2, 2, 8, 5];
// Size of array arr[]
var n = arr.length;
// Function call to get cnt
var cnt = sortByFreq(arr, n);
// Sort the arr[] in decreasing order
arr.sort((a, b) => b - a);
// Function that prints elements
// in decreasing order
printSortedArray(arr, cnt);
</script>
Producción:
4 4 4 2 2 5 5 6 8
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Enfoque basado en pares y comparadores STL :
Acercarse:
1. Almacena la frecuencia de cada elemento en un mapa.
2. Iterar el mapa y almacenar cada elemento y su frecuencia en un vector de pares.
3. Pasar un comparador que clasifique los elementos en orden decreciente de su frecuencia y por valor de los elementos si la frecuencia es igual.
4. Empuje los elementos su número de veces de frecuencia dentro de la array final.
C++
#include<bits/stdc++.h>
using namespace std;
bool compare(pair<int,int>p1,pair<int,int>p2)
{
if(p1.second==p2.second) //if frequency is equal
{
return p1.first<p2.first; //return the smaller value
}
return p1.second>p2.second; //return the element with greater frequency
}
int main()
{
vector<int>arr={4,4,5,6,4,2,2,8,5};
int n=arr.size();
map<int,int>m;
for(int i=0;i<n;i++)
{
m[arr[i]]+=1;
}
vector<pair<int,int>>a;
for(auto it=m.begin();it!=m.end();it++)
{
a.push_back(make_pair(it->first,it->second)); //making pair of element and it's frequency
}
sort(a.begin(),a.end(),compare);
vector<int>ans;
for(auto x:a)
{
while(x.second--)
{
ans.push_back(x.first);
}
}
for(auto x:ans)
{
cout<<x<<" ";
}
return 0;
}
Python3
# Python code for the approach
from functools import cmp_to_key
def compare(p1, p2):
if(p1[1] == p2[1]): #if frequency is equal
return p1[0] - p2[0] #return the smaller value
return p2[1] - p1[1] #return the element with greater frequency
# driver code
arr = [4, 4, 5, 6, 4, 2, 2, 8, 5]
n = len(arr)
m = {}
for i in range(n):
if(arr[i] in m):
m[arr[i]] = m[arr[i]] + 1
else:
m[arr[i]] = 1
a = []
for x,y in m.items():
a.append([x,y]) #making pair of element and it's frequency
a.sort(key = cmp_to_key(compare))
ans = []
for x in a:
while(x[1]):
ans.append(x[0])
x[1] -= 1
for x in ans:
print(x, end = " ")
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript code for the approach
function compare(p1, p2)
{
if(p1[1] == p2[1]) //if frequency is equal
{
return p1[0] - p2[0]; //return the smaller value
}
return p2[1] - p1[1]; //return the element with greater frequency
}
// driver code
let arr = [4,4,5,6,4,2,2,8,5];
let n = arr.length;
let m = new Map();
for(let i = 0; i < n; i++)
{
if(m.has(arr[i])){
m.set(arr[i], m.get(arr[i]) + 1);
}
else m.set(arr[i],1);
}
let a = [];
for(let [x,y] of m)
{
a.push([x,y]); //making pair of element and it's frequency
}
a.sort(compare);
let ans = [];
for(let x of a){
while(x[1]--){
ans.push(x[0]);
}
}
for(let x of ans)
{
document.write(x," ");
}
// This code is contributed by shinjanpatra
</script>
Producción
4 4 4 2 2 5 5 6 8
Publicación traducida automáticamente
Artículo escrito por kartikagra2014 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA