Encuentre la frecuencia de cada elemento en una array 3D dada

Dada una array 3D de tamaño N*M*P que consta solo de caracteres del alfabeto inglés, la tarea es imprimir la frecuencia de todos los elementos en orden creciente. Si la frecuencia es la misma, imprímalas en orden lexicográfico.

Ejemplos:

Entrada: N = 3, M = 4, P = 5,  
array = { { {a, b, c, d, e}, {f, g, h, i, k}, {a, c, d, e , s}, {e, g, e, s, j} },  
                 { {s, j, r, s, g}, {s, t, u, e, y}, {t, y, g, j , l}, {d, r, g, t, j } },  
                { {e, y, r, v, n}, {q, r, y, e, w}, {k, e, u, p , q}, {z, v, a, s, d} } }
Salida:
b 1
f 1
h 1
i 1
l 1
n 1
p 1
w 1
z 1
c 2
k 2
q 2
u 2
v 2
a 3
t 3
re 4
j 4
r 4
y 4
g 5
s 6
e 8

Entrada: N = 1, M = 1, P = 3,  
array = { { { a, b, a} } } } 
Salida: 
a 2
b 1

Enfoque: este problema se puede resolver fácilmente utilizando Hashing and Sorting .  

• Cree una tabla hash usando el mapa para almacenar la frecuencia de todos los caracteres en la array.
• La clave en un mapa siempre está ordenada.
• Atraviese la array e incremente la frecuencia del carácter en esa posición.
• Empuje las frecuencias en un vector (digamos v ) con sus respectivos caracteres.
• Ordene el vector de frecuencia v según la frecuencia.

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

// C++ code to implement the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find frequency in 3-D matrix
void findFreq(int X, int Y, int Z,
              vector<vector<vector<char> > >& matrix)
{
    // Initializing unordered map
    unordered_map<char, int> freq;
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < Y; j++) {
            for (int k = 0; k < Z; k++) {
                freq[matrix[i][j][k]]++;
            }
        }
    }
 
    // Store the frequency in vector
    vector<pair<int, char> > v;
    for (auto p : freq) {
        v.push_back({ p.second, p.first });
    }
 
    // Sort the frequency vector
    sort(v.begin(), v.end());
 
    for (auto p : v)
        cout << p.second << " " << p.first << endl;
}
 
// Drivers code
int main()
{
    int X = 3, Y = 4, Z = 5;
 
    // Declare 3D array of characters
    vector<vector<vector<char> > > matrix = {
        { { 'a', 'b', 'c', 'd', 'e' },
          { 'f', 'g', 'h', 'i', 'k' },
          { 'a', 'c', 'd', 'e', 's' },
          { 'e', 'g', 'e', 's', 'j' } },
        { { 's', 'j', 'r', 's', 'g' },
          { 's', 't', 'u', 'e', 'y' },
          { 't', 'y', 'g', 'j', 'l' },
          { 'd', 'r', 'g', 't', 'j' } },
        { { 'e', 'y', 'r', 'v', 'n' },
          { 'q', 'r', 'y', 'e', 'w' },
          { 'k', 'e', 'u', 'p', 'q' },
          { 'z', 'v', 'a', 's', 'd' } }
    };
 
    // Function call
    findFreq(X, Y, Z, matrix);
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
  // Function to find frequency in 3-D matrix
  static void findFreq(int X, int Y, int Z,
                       char[][][] matrix)
  {
 
    // Initializing unordered map
    HashMap<Character, Integer> freq = new HashMap<>();
    for (int i = 0; i < X; i++) {
      for (int j = 0; j < Y; j++) {
        for (int k = 0; k < Z; k++) {
          if (!freq.containsKey(matrix[i][j][k]))
            freq.put(matrix[i][j][k], 1);
          else
            freq.put(matrix[i][j][k],
                     freq.get(matrix[i][j][k])
                     + 1);
        }
      }
    }
 
    // Get the size of the freq hashmap
    // to declare a new array
    int size = freq.size();
 
    // Store the frequency in 2d array v
    int[][] v = new int[size][2];
    int index = 0;
 
    for (Map.Entry mapElement : freq.entrySet()) {
      v[index][0] = (char)mapElement.getKey();
      v[index][1] = (int)mapElement.getValue();
      index++;
    }
 
    // Sort the frequency array
    // based on the frequencies
    Arrays.sort(v,
                (a, b) -> Integer.compare(a[1], b[1]));
 
    for (int i = 0; i < size; i++) {
      System.out.println((char)v[i][0] + " "
                         + v[i][1]);
    }
  }
  public static void main(String[] args)
  {
     
    // Drivers code
    int X = 3, Y = 4, Z = 5;
 
    // Declare 3D array of characters
    char[][][] matrix
      = { { { 'a', 'b', 'c', 'd', 'e' },
           { 'f', 'g', 'h', 'i', 'k' },
           { 'a', 'c', 'd', 'e', 's' },
           { 'e', 'g', 'e', 's', 'j' } },
         { { 's', 'j', 'r', 's', 'g' },
          { 's', 't', 'u', 'e', 'y' },
          { 't', 'y', 'g', 'j', 'l' },
          { 'd', 'r', 'g', 't', 'j' } },
         { { 'e', 'y', 'r', 'v', 'n' },
          { 'q', 'r', 'y', 'e', 'w' },
          { 'k', 'e', 'u', 'p', 'q' },
          { 'z', 'v', 'a', 's', 'd' } } };
 
    // Function call
    findFreq(X, Y, Z, matrix);
  }
}
 
// this code is contributed by phasing17

# Python3 code to implement the above approach
 
# Function to find frequence in 3-D matrix
def findFreq(X, Y, Z, matrix):
 
    # initializing the dictionary
    freq = dict()
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                if matrix[i][j][k] in freq:
                    freq[matrix[i][j][k]] += 1
                else:
                    freq[matrix[i][j][k]] = 1
 
    # store the frequency in v
    v = []
    for p in freq:
        v.append([freq[p], p])
 
    # sort the frequency vector
    v.sort()
 
    for p in v:
        print(p[1], p[0])
 
# Driver Code
X, Y, Z = 3, 4, 5
 
# Declare 3D array of characters
matrix = [[['a', 'b', 'c', 'd', 'e'],
           ['f', 'g', 'h', 'i', 'k'],
           ['a', 'c', 'd', 'e', 's'],
           ['e', 'g', 'e', 's', 'j']],
          [['s', 'j', 'r', 's', 'g'],
           ['s', 't', 'u', 'e', 'y'],
           ['t', 'y', 'g', 'j', 'l'],
           ['d', 'r', 'g', 't', 'j']],
          [['e', 'y', 'r', 'v', 'n'],
           ['q', 'r', 'y', 'e', 'w'],
           ['k', 'e', 'u', 'p', 'q'],
           ['z', 'v', 'a', 's', 'd']]]
 
# Function Call
findFreq(X, Y, Z, matrix)
 
# This code is contributed by phasing17

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to find frequency in 3-D matrix
  static void findFreq(int X, int Y, int Z,
                       char[][][] matrix)
  {
 
    // Initializing unordered map
    Dictionary<char, int> freq = new Dictionary<char, int>();
 
    for (int i = 0 ; i < X ; i++) {
      for (int j = 0 ; j < Y ; j++) {
        for (int k = 0 ; k < Z ; k++) {
          if (!freq.ContainsKey(matrix[i][j][k])){
            freq.Add(matrix[i][j][k], 1);
          }else{
            freq[matrix[i][j][k]] += 1;
          }
        }
      }
    }
 
    // Get the size of the freq hashmap
    // to declare a new array
    int size = freq.Count;
 
    // Store the frequency in 2d array v
    pair[] v = new pair[size];
    for(int i = 0 ; i < size ; i++){
      v[i] = new pair(0, 0);
    }
 
    int index = 0;
    foreach (KeyValuePair<char, int> mapElement in freq){
      v[index].first = (int)mapElement.Key;
      v[index].second = mapElement.Value;
      index++;
    }
 
    // Sort the frequency array
    // based on the frequencies
    Array.Sort(v, new Comp());
 
    for (int i = 0; i < size; i++) {
      Console.WriteLine((char)v[i].first + " " + v[i].second);
    }
  }
 
  public static void Main(string[] args){
 
    // Drivers code
    int X = 3, Y = 4, Z = 5;
 
    // Declare 3D array of characters
    char[][][] matrix = new char[][][]{
      new char[][]{
        new char[]{ 'a', 'b', 'c', 'd', 'e' },
        new char[]{ 'f', 'g', 'h', 'i', 'k' },
        new char[]{ 'a', 'c', 'd', 'e', 's' },
        new char[]{ 'e', 'g', 'e', 's', 'j' }
      },
      new char[][]{
        new char[]{ 's', 'j', 'r', 's', 'g' },
        new char[]{ 's', 't', 'u', 'e', 'y' },
        new char[]{ 't', 'y', 'g', 'j', 'l' },
        new char[]{ 'd', 'r', 'g', 't', 'j' }
      },
      new char[][]{
        new char[]{ 'e', 'y', 'r', 'v', 'n' },
        new char[]{ 'q', 'r', 'y', 'e', 'w' },
        new char[]{ 'k', 'e', 'u', 'p', 'q' },
        new char[]{ 'z', 'v', 'a', 's', 'd' }
      }
    };
 
    // Function call
    findFreq(X, Y, Z, matrix);
 
  }
}
 
// Class for pair
public class pair{
  public int first;
  public int second;
 
  // Constructor
  public pair(int f, int s)
  {
    this.first = f;
    this.second = s;
  }
}
 
class Comp : IComparer<pair>{
  public int Compare(pair a, pair b)
  {
    if(a.second == b.second){
      return a.first-b.first;
    }
    return a.second-b.second;
  }
}
 
// This code is contributed by subhamgoyal2014.

<script>
 
// JavaScript implementation of the above approach
 
// Function to find frequency in 3-D matrix
function findFreq(X, Y, Z,matrix)
{
    // Initializing unordered map
    let freq = new Map();
    for (let i = 0; i < X; i++) {
        for (let j = 0; j < Y; j++) {
            for (let k = 0; k < Z; k++) {
                if(!freq.has(matrix[i][j][k]))
                    freq.set(matrix[i][j][k],1)
                else
                    freq.set(matrix[i][j][k],freq.get(matrix[i][j][k])+1)
            }
        }
    }
 
    // Store the frequency in vector
    let v = [];
    for (let [p,q] of freq) {
        v.push([q,p]);
    }
 
    // Sort the frequency vector
    v.sort();
 
    for (let p of v)
        document.write(`${p[1]} ${p[0]}`,"</br>");
}
 
// Drivers code
 
let X = 3, Y = 4, Z = 5;
 
// Declare 3D array of characters
let matrix = [
        [ [ 'a', 'b', 'c', 'd', 'e' ],
          [ 'f', 'g', 'h', 'i', 'k' ],
          [ 'a', 'c', 'd', 'e', 's' ],
          [ 'e', 'g', 'e', 's', 'j' ] ],
        [ [ 's', 'j', 'r', 's', 'g' ],
          [ 's', 't', 'u', 'e', 'y' ],
          [ 't', 'y', 'g', 'j', 'l' ],
          [ 'd', 'r', 'g', 't', 'j' ] ],
        [ [ 'e', 'y', 'r', 'v', 'n' ],
          [ 'q', 'r', 'y', 'e', 'w' ],
          [ 'k', 'e', 'u', 'p', 'q' ],
          [ 'z', 'v', 'a', 's', 'd' ] ]
];
 
// Function call
findFreq(X, Y, Z, matrix);
 
// This code is written by
// shinjanpatra
 
</script>

b 1
f 1
h 1
i 1
l 1
n 1
p 1
w 1
z 1
c 2
k 2
q 2
u 2
v 2
a 3
t 3
d 4
j 4
r 4
y 4
g 5
s 6
e 8

Complejidad del tiempo:O(N*M*P)
Espacio Auxiliar:O(1) Como el mapa tendrá como máximo 26 valores