Ordenar elemento de una array por frecuencia en orden decreciente

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 8

Entrada: 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *