Dada una array arr[] de tamaño N y un número entero K que representa un dígito, la tarea es imprimir la array dada en orden creciente de acuerdo con la frecuencia creciente del dígito K en los elementos de la array .
Ejemplos:
Entrada: arr[] = {15, 66, 26, 91}, K = 6
Salida: 15 91 26 66
Explicación:
La frecuencia del dígito 6 en los elementos de la array es {0, 2, 1, 0}. Los elementos en orden creciente de frecuencia del dígito 6 en {15, 91, 26, 66}.Entrada: arr[] = {20, 21, 0}, K = 0
Salida: 21 20 0
Explicación:
La frecuencia del dígito 0 en los elementos de la array es {1, 0, 1}. Los elementos en orden creciente de frecuencia del dígito 0 son {21, 20, 0}.
Enfoque: La idea es contar las ocurrencias del dígito K para cada elemento de la array y ordenar la array de acuerdo con ello. Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa múltiple , digamos mp , para almacenar las ocurrencias de K en cada elemento en orden ordenado.
- Recorra la array dada arr[] usando la variable i y realice lo siguiente:
- Almacene las ocurrencias del dígito K en arr[i] en una variable cnt .
- Inserte un par de cnt y arr[i] en mp .
- Imprima los elementos de la array en mp para obtener el orden ordenado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the occurrences
// of digit K in an element
int countOccurrences(int num, int K)
{
// If num and K are both 0
if (K == 0 && num == 0)
return 1;
// Initialize count as 0
int count = 0;
// Count for occurrences of digit K
while (num > 0) {
if (num % 10 == K)
count++;
num /= 10;
}
// Return the count
return count;
}
// Function to print the given array
// in increasing order of the digit
// K in the array elements
void sortOccurrences(int arr[],
int N, int K)
{
// Stores the occurrences of K
// in each element
multimap<int, int> mp;
// Traverse the array
for (int i = 0; i < N; i++) {
// Count the frequency
// of K in arr[i]
int count = countOccurrences(
arr[i], K);
// Insert elements in mp
mp.insert(pair<int, int>(
count, arr[i]));
}
// Print the elements in the map, mp
for (auto& itr : mp) {
cout << itr.second << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 15, 66, 26, 91 };
int K = 6;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
sortOccurrences(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to count the occurrences
// of digit K in an element
static int countOccurrences(int num, int K)
{
// If num and K are both 0
if (K == 0 && num == 0)
return 1;
// Initialize count as 0
int count = 0;
// Count for occurrences of digit K
while (num > 0) {
if (num % 10 == K)
count++;
num /= 10;
}
// Return the count
return count;
}
// Pair class
static class Pair {
int idx;
int freq;
Pair(int idx, int freq)
{
this.idx = idx;
this.freq = freq;
}
}
// Function to print the given array
// in increasing order of the digit
// K in the array elements
static void sortOccurrences(int arr[], int N, int K)
{
// Stores the Pair with index
// and occurrences of K of each element
Pair mp[] = new Pair[N];
// Traverse the array
for (int i = 0; i < N; i++) {
// Count the frequency
// of K in arr[i]
int count = countOccurrences(arr[i], K);
// Insert Pair in mp
mp[i] = new Pair(i, count);
}
// sort the mp in increasing order of freq
// if freq equal then according to index
Arrays.sort(mp, (p1, p2) -> {
if (p1.freq == p2.freq)
return p1.idx - p2.idx;
return p1.freq - p2.freq;
});
// Print the elements in the map, mp
for (Pair p : mp) {
System.out.print(arr[p.idx] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 15, 66, 26, 91 };
int K = 6;
int N = arr.length;
// Function Call
sortOccurrences(arr, N, K);
}
}
// This code is contributed by Kingash.
Python3
# Python program for the above approach # Function to count the occurrences # of digit K in an element def countOccurrences( num, K): # If num and K are both 0 if (K == 0 and num == 0): return 1 # Initialize count as 0 count = 0 # Count for occurrences of digit K while (num > 0): if (num % 10 == K): count += 1 num //= 10 # Return the count return count # Function to print the given array # in increasing order of the digit # K in the array elements def sortOccurrences(arr, N, K): # Stores the occurrences of K # in each element mp = [] # Traverse the array for i in range(N): # Count the frequency # of K in arr[i] count = countOccurrences(arr[i], K) # Insert elements in mp mp.append([count, arr[i]]) # Print the elements in the map, mp mp = sorted(mp) for itr in mp: print(itr[1], end = ' ') # Driver Code arr = [ 15, 66, 26, 91 ] K = 6 N = len(arr) # Function Call sortOccurrences(arr, N, K); # This code is contributed by rohitsingh07052.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to count the occurrences
// of digit K in an element
static int countOccurrences(int num, int K)
{
// If num and K are both 0
if (K == 0 && num == 0)
return 1;
// Initialize count as 0
int count = 0;
// Count for occurrences of digit K
while (num > 0) {
if (num % 10 == K)
count++;
num /= 10;
}
// Return the count
return count;
}
// Pair class
class Pair : IComparable<Pair> {
public int idx;
public int freq;
public Pair(int idx, int freq)
{
this.idx = idx;
this.freq = freq;
}
public int CompareTo(Pair p)
{
if (this.freq == p.freq)
return this.idx - p.idx;
return this.freq - p.freq;
}
}
// Function to print the given array
// in increasing order of the digit
// K in the array elements
static void sortOccurrences(int []arr, int N, int K)
{
// Stores the Pair with index
// and occurrences of K of each element
Pair []mp = new Pair[N];
// Traverse the array
for (int i = 0; i < N; i++) {
// Count the frequency
// of K in arr[i]
int count = countOccurrences(arr[i], K);
// Insert Pair in mp
mp[i] = new Pair(i, count);
}
// sort the mp in increasing order of freq
// if freq equal then according to index
Array.Sort(mp);
// Print the elements in the map, mp
foreach (Pair p in mp) {
Console.Write(arr[p.idx] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 15, 66, 26, 91 };
int K = 6;
int N = arr.Length;
// Function Call
sortOccurrences(arr, N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to count the occurrences
// of digit K in an element
function countOccurrences( num, K){
// If num and K are both 0
if (K == 0 && num == 0)
return 1
// Initialize count as 0
count = 0
// Count for occurrences of digit K
while (num > 0){
if (num % 10 == K)
count += 1
num = Math.floor(num/10)
}
// Return the count
return count
}
// Function to print the given array
// in increasing order of the digit
// K in the array elements
function sortOccurrences(arr, N, K){
// Stores the occurrences of K
// in each element
mp = []
// Traverse the array
for(let i=0;i<N;i++){
// Count the frequency
// of K in arr[i]
let count = countOccurrences(arr[i], K)
// Insert elements in mp
mp.push([count, arr[i]])
}
// Print the elements in the map, mp
mp.sort()
for([itr1,itr2] of mp)
document.write(itr2,' ')
}
// Driver Code
let arr = [ 15, 66, 26, 91 ]
let K = 6
let N = arr.length
// Function Call
sortOccurrences(arr, N, K)
// This code is contributed by shinjanpatra
</script>
Producción:
15 91 26 66
Complejidad de tiempo: O(N*log 10 N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA