Frecuencia acumulativa de conteo de cada elemento en una array no ordenada – Part 1

Dada una array no ordenada. La tarea es calcular la frecuencia acumulada de cada elemento de la array utilizando una array de conteo.

Ejemplos:  

Input : arr[] = [1, 2, 2, 1, 3, 4]
Output :1->2
        2->4
        3->5
        4->6

Input : arr[] = [1, 1, 1, 2, 2, 2]
Output :1->3
        2->6 

Una solución simple es usar dos bucles anidados. El bucle exterior elige un elemento de izquierda a derecha que no se visita. El bucle interno cuenta sus ocurrencias y marca las ocurrencias como visitadas. La complejidad temporal de esta solución es O(n*n) y el espacio auxiliar requerido es O(n).

Una mejor solución es utilizar la clasificación. Ordenamos la array para que los mismos elementos se unan. Después de ordenar, recorremos linealmente los elementos y contamos sus frecuencias.

Una solución eficiente es usar hashing. Inserte el elemento y su frecuencia en un conjunto de pares. Como el conjunto almacena valores únicos en un orden ordenado, almacenará todos los elementos con sus frecuencias en un orden ordenado. Iterar en el conjunto e imprimir las frecuencias sumando las anteriores en cada paso. 

A continuación se muestra la implementación del enfoque anterior: 

#include <bits/stdc++.h>
using namespace std;
 
// Function to print the cumulative frequency according to
// the order given
void countFreq(int a[], int n)
{
   
    // Declaring a map so values get inserted in a sorted
    // manner
    map<int, int> m;
   
    // Inserting values into the map
    for (int i = 0; i < n; i++) {
        m[a[i]]++;
    }
   
    // Variable to store the count of previous number
    // cumulative frequency
    int cumul = 0;
    for (auto v : m) {
        cout << v.first << " " << v.second + cumul
             << endl;
        cumul += v.second;
    }
}
 
int main()
{
    int arr[] = { 1, 3, 2, 4, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    countFreq(arr, n);
    return 0;
}
 
// This code is contributed by Vinayak Pareek (Kargil)

// Java program to count cumulative
// frequencies of elements in an unsorted array.
import java.util.*;
 
class GFG
{
    static void countFreq(int[] a, int n)
    {
 
        // Insert elements and their
        // frequencies in hash map.
        HashMap<Integer,
                Integer> hm = new HashMap<>();
        for (int i = 0; i < n; i++)
            hm.put(a[i], hm.get(a[i]) == null ?
                     1 : hm.get(a[i]) + 1);
 
        // Declare a Map
        SortedMap<Integer, Integer> st = new TreeMap<>();
 
        // insert the element and
        // and insert its frequency in a set
        for (HashMap.Entry<Integer,
                           Integer> x : hm.entrySet())
        {
            st.put(x.getKey(), x.getValue());
        }
 
        int cumul = 0;
 
        // iterate the set and print the
        // cumulative frequency
        for (SortedMap.Entry<Integer,
                             Integer> x : st.entrySet())
        {
            cumul += x.getValue();
            System.out.println(x.getKey() + " " + cumul);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] a = { 1, 3, 2, 4, 2, 1 };
        int n = a.length;
        countFreq(a, n);
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 program to count cumulative
# frequencies of elements in an unsorted array.
def countFreq(a, n):
 
    # Insert elements and their
    # frequencies in hash map.
    hm = {}
    for i in range(0, n):
        hm[a[i]] = hm.get(a[i], 0) + 1
 
    # Declare a set
    st = set()
 
    # Insert the element and
    # its frequency in a set
    for x in hm:
        st.add((x, hm[x]))
 
    cumul = 0
 
    # Iterate the set and print
    # the cumulative frequency
    for x in sorted(st):
        cumul += x[1]
        print(x[0], cumul)
 
# Driver Code
if __name__ == "__main__":
 
    a = [1, 3, 2, 4, 2, 1]
    n = len(a)
    countFreq(a, n)
     
# This code is contributed by Rituraj Jain

// C# program to count cumulative
// frequencies of elements in an
// unsorted array.
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG{
     
static void countFreq(int[] a, int n)
{
     
    // Insert elements and their
    // frequencies in hash map.
    Dictionary<int,
               int> hm = new Dictionary<int,
                                        int>();
    for(int i = 0; i < n; i++)
    {
        if (hm.ContainsKey(a[i]))
        {
            hm[a[i]]++;
        }
        else
        {
            hm[a[i]] = 1;
        }
    }
 
    int cumul = 0;
 
    // Iterate the set and print the
    // cumulative frequency
    foreach(KeyValuePair<int,
                         int> x in hm.OrderBy(key => key.Key))
    {
        cumul += x.Value;
        Console.Write(x.Key + " " + cumul + "\n");
    }
}
 
// Driver Code
public static void Main(string[] args)
{
    int[] a = { 1, 3, 2, 4, 2, 1 };
    int n = a.Length;
     
    countFreq(a, n);
}
}
 
// This code is contributed by rutvik_56

<script>
// Javascript program to count cumulative
// frequencies of elements in an unsorted array.
     
    function countFreq(a,n)
    {
        // Insert elements and their
        // frequencies in hash map.
        let hm = new Map();
        for (let i = 0; i < n; i++)
            hm.set(a[i], hm.get(a[i]) == null ?
                     1 : hm.get(a[i]) + 1);
   
        // Declare a Map
        let st = new Set();
           
        // insert the element and
        // and insert its frequency in a set
        for (let [key, value] of hm.entries())
        {   
            st.add([key, value]);
        }
          st=[...st.entries()].sort()
        let cumul = 0;
   
        // iterate the set and print the
        // cumulative frequency
        for (let [key, value] of st.entries())
        {
            cumul += value[1][1];
            document.write(value[1][0] + " " + cumul+"<br>");
        }
    }
     
    // Driver Code
    let a=[1, 3, 2, 4, 2, 1];
    let n = a.length;
    countFreq(a, n);
     
 
// This code is contributed by unknown2108
</script>

1 2
2 4
3 5
4 6

La complejidad temporal de la solución es O(n log n) .

¿Qué pasa si necesitamos frecuencias de elementos según el orden de la primera aparición?  
Por ejemplo, una array [2, 4, 1, 2, 1, 3, 4], primero se debe imprimir la frecuencia de 2, luego de 4, luego 1 y finalmente 3. 

Enfoque: hash el recuento de ocurrencias de un elemento. Recorra la array e imprima la frecuencia acumulada. Una vez que se imprimió el elemento y su frecuencia acumulada, haga un hash de la ocurrencia de ese elemento como 0 para que no se vuelva a imprimir si aparece en la última mitad de la array durante el recorrido. 

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to print the cumulative frequency
// according to the order given
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the cumulative frequency
// according to the order given
void countFreq(int a[], int n)
{
    // Insert elements and their
    // frequencies in hash map.
    unordered_map<int, int> hm;
    for (int i=0; i<n; i++)
        hm[a[i]]++;
    int cumul = 0;
     
   // traverse in the array
   for(int i=0;i<n;i++)
   {
       // add the frequencies
       cumul += hm[a[i]];
        
       // if the element has not been
       // visited previously
       if(hm[a[i]])
       {
           cout << a[i] << "->" << cumul << endl;
       }
       // mark the hash 0
       // as the element's cumulative frequency
       // has been printed
       hm[a[i]]=0;
   }
}
 
// Driver Code
int main()
{
    int a[] = {1, 3, 2, 4, 2, 1};
    int n = sizeof(a)/sizeof(a[0]);
    countFreq(a, n);
    return 0;
}

// Java program to print the cumulative frequency
// according to the order given
class GFG
{
 
// Function to print the cumulative frequency
// according to the order given
static void countFreq(int a[], int n)
{
    // Insert elements and their
    // frequencies in hash map.
    int hm[] = new int[n];
    for (int i = 0; i < n; i++)
        hm[a[i]]++;
    int cumul = 0;
     
// traverse in the array
for(int i = 0; i < n; i++)
{
    // add the frequencies
    cumul += hm[a[i]];
         
    // if the element has not been
    // visited previously
    if(hm[a[i]] != 0)
    {
        System.out.println(a[i] + "->" + cumul);
    }
    // mark the hash 0
    // as the element's cumulative frequency
    // has been printed
    hm[a[i]] = 0;
}
}
 
// Driver Code
public static void main(String[] args)
{
    int a[] = {1, 3, 2, 4, 2, 1};
    int n = a.length;
    countFreq(a, n);
}
}
 
// This code has been contributed by 29AjayKumar

# Python3 program to print the cumulative
# frequency according to the order given
 
# Function to print the cumulative frequency
# according to the order given
def countFreq(a, n):
 
    # Insert elements and their
    # frequencies in hash map.
    hm = dict()
    for i in range(n):
        hm[a[i]] = hm.get(a[i], 0) + 1
 
    cumul = 0
 
    # traverse in the array
    for i in range(n):
 
    # add the frequencies
        cumul += hm[a[i]]
 
    # if the element has not been
    # visited previously
        if(hm[a[i]] > 0):
            print(a[i], "->", cumul)
             
    # mark the hash 0
    # as the element's cumulative
    # frequency has been printed
        hm[a[i]] = 0
 
# Driver Code
a = [1, 3, 2, 4, 2, 1]
n = len(a)
countFreq(a, n)
 
# This code is contributed by mohit kumar

// C# program to print the cumulative frequency
// according to the order given
using System;
 
class GFG
{
 
// Function to print the cumulative frequency
// according to the order given
static void countFreq(int []a, int n)
{
    // Insert elements and their
    // frequencies in hash map.
    int []hm = new int[n];
    for (int i = 0; i < n; i++)
        hm[a[i]]++;
    int cumul = 0;
     
// traverse in the array
for(int i = 0; i < n; i++)
{
    // add the frequencies
    cumul += hm[a[i]];
         
    // if the element has not been
    // visited previously
    if(hm[a[i]] != 0)
    {
        Console.WriteLine(a[i] + "->" + cumul);
    }
     
    // mark the hash 0
    // as the element's cumulative frequency
    // has been printed
    hm[a[i]] = 0;
}
}
 
// Driver Code
public static void Main(String[] args)
{
    int []a = {1, 3, 2, 4, 2, 1};
    int n = a.Length;
    countFreq(a, n);
}
}
 
/* This code contributed by PrinciRaj1992 */

<script>
// Javascript program to print the cumulative frequency
// according to the order given
     
// Function to print the cumulative frequency
// according to the order given
function countFreq(a,n) {
    // Insert elements and their
    // frequencies in hash map.
    let hm = new Array(n);
    for(let i=0;i<hm.length;i++)
    {
        hm[i]=0;
    }
    for (let i = 0; i < n; i++)
        hm[a[i]]++;
    let cumul = 0;
       
    // traverse in the array
    for(let i = 0; i < n; i++)
    {
        // add the frequencies
        cumul += hm[a[i]];
           
        // if the element has not been
        // visited previously
        if(hm[a[i]] != 0)
        {
            document.write(a[i] + "->" + cumul+"<br>");
        }
        // mark the hash 0
        // as the element's cumulative frequency
        // has been printed
        hm[a[i]] = 0;
    }
  
}
  
// Driver Code
let a=[1, 3, 2, 4, 2, 1];
let n = a.length;
countFreq(a, n);
     
 
// This code is contributed by patel2127
</script>

1->2
3->3
2->5
4->6

Complejidad de tiempo: O(n), donde n es el tamaño de la array dada
Espacio auxiliar: O(n), ya que el espacio adicional de tamaño n se usa para crear un mapa

Este artículo es una contribución de Himanshu Ranjan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.