Dada una string str , la tarea es ordenar la string según la frecuencia de cada carácter, en orden ascendente. Si dos elementos tienen la misma frecuencia, se clasifican en orden lexicográfico.
Ejemplos:
Entrada: str = “geeksforgeeks”
Salida: forggkksseeee
Explicación:
Frecuencia de caracteres: g2 e4 k2 s2 f1 o1 r1
Caracteres ordenados según la frecuencia: f1 o1 r1 g2 k2 s2 e4
f, o, r aparecen una vez por lo que se ordenan lexicográficamente y también lo son g, k y s.
Por lo tanto, el resultado final es forggkksseeee .
Entrada: str = “abc”
Salida: abc
Enfoque La idea es almacenar cada carácter con su frecuencia en un vector de pares y luego clasificar los pares de vectores según la frecuencia almacenada. Finalmente, imprima el vector en orden.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Sort strings
// according to the frequency of
// characters in ascending order
#include <bits/stdc++.h>
using namespace std;
// Returns count of character in the string
int countFrequency(string str, char ch)
{
int count = 0;
for (int i = 0; i < str.length(); i++)
// Check for vowel
if (str[i] == ch)
++count;
return count;
}
// Function to sort the string
// according to the frequency
void sortArr(string str)
{
int n = str.length();
// Vector to store the frequency of
// characters with respective character
vector<pair<int, char> > vp;
// Inserting frequency
// with respective character
// in the vector pair
for (int i = 0; i < n; i++) {
vp.push_back(
make_pair(
countFrequency(str, str[i]),
str[i]));
}
// Sort the vector, this will sort the pair
// according to the number of characters
sort(vp.begin(), vp.end());
// Print the sorted vector content
for (int i = 0; i < vp.size(); i++)
cout << vp[i].second;
}
// Driver code
int main()
{
string str = "geeksforgeeks";
sortArr(str);
return 0;
}
Python3
# Python3 implementation to Sort strings # according to the frequency of # characters in ascending order # Returns count of character in the string def countFrequency(string , ch) : count = 0; for i in range(len(string)) : # Check for vowel if (string[i] == ch) : count += 1; return count; # Function to sort the string # according to the frequency def sortArr(string) : n = len(string); # Vector to store the frequency of # characters with respective character vp = []; # Inserting frequency # with respective character # in the vector pair for i in range(n) : vp.append((countFrequency(string, string[i]), string[i])); # Sort the vector, this will sort the pair # according to the number of characters vp.sort(); # Print the sorted vector content for i in range(len(vp)) : print(vp[i][1],end=""); # Driver code if __name__ == "__main__" : string = "geeksforgeeks"; sortArr(string); # This code is contributed by Yash_R
Javascript
<script>
// JavaScript implementation of the above approach
// Returns count of character in the string
function countFrequency(str, ch)
{
var count = 0;
for (var i = 0; i < str.length; i++)
// Check for vowel
if (str[i] == ch)
++count;
return count;
}
// Function to sort the string
// according to the frequency
function sortArr(str)
{
var n = str.length;
// Vector to store the frequency of
// characters with respective character
vp = new Array(n);
// Inserting frequency
// with respective character
// in the vector pair
for (var i = 0; i < n; i++) {
vp[i] = [countFrequency(str, str[i]), str[i]];
}
// Sort the vector, this will sort the pair
// according to the number of characters
vp.sort();
// Print the sorted vector content
for (var i = 0; i < n; i++)
document.write(vp[i][1]);
}
// Driver Code
// Array of points
let str = "geeksforgeeks";
sortArr(str);
</script>
forggkksseeee
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n)
Método 2: (Enfoque optimizado: basado en almacenamiento dinámico mínimo)
Algoritmo:
1. Tome la frecuencia de cada carácter en un mapa.
2. Tome un MIN Heap, guárdelo en FREQUENCY, CHAR
3. Después de todas las inserciones, el elemento superior es el carácter menos frecuente
4. Mantenemos un COMPARADOR PERSONALIZADO para MENOS FRECUENCIA, CUANDO MISMA FRECUENCIA – Caracteres de Orden Ascendente.
5. Luego haga estallar uno por uno y agregue ANS String para FREQ no. de tiempos
CÓDIGO:
C++
#include <bits/stdc++.h>
using namespace std;
//O(N*LogN) Time, O(Distinct(N)) Space
//MIN HEAP Based - as we need less frequent element first
#define ppi pair<int,char>
//CUSTOM COMPARATOR for Heap
class Compare{
public:
//Override
bool operator()(pair<int,char>below, pair<int,char> above){
if(below.first == above.first){
//freq same
return below.second > above.second; //lexicographicaly smaller is TOP
}
return below.first > above.first; //less freq at TOP
}
};
string frequencySort(string s) {
unordered_map<char,int> mpp;
priority_queue<ppi,vector<ppi>,Compare> minH; // freq , character
for(char ch : s){
mpp[ch]++;
}
for(auto m : mpp){
minH.push({m.second, m.first}); // as freq is 1st , char is 2nd
}
string ans="";
//Now we have in the TOP - Less Freq chars
while(minH.size()>0){
int freq = minH.top().first;
char ch = minH.top().second;
for(int i=0; i<freq; i++){
ans+=ch; // append as many times of freq
}
minH.pop(); //Heapify happens
}
return ans;
}
// Driver code
int main()
{
string str = "geeksforgeeks";
cout<<frequencySort(str)<<"\n";
return 0;
}
//Code is Contributed by Balakrishnan R (rbkraj000)
forggkksseeee
Complejidad del tiempo:
O(N+ N* Registro N + N* Registro N) = O(N* Registro N)
Razón:
- 1 inserción en el montón toma O (Log N), para N inserciones O (N * LogN). (HEAP = cola de prioridad)
- 1 eliminación en el montón toma O (Log N), para N inserciones O (N * LogN).
- El mapa desordenado toma O(1) para 1 inserción.
- N es la longitud de la string S (entrada)
Complejidad de espacio adicional:
EN)
Razón:
- El mapa toma O(Distinto(N)) Espacio.
- Heap también toma O(Distinct(N)) Space.
- N es la longitud de la string S (entrada)
El Código, el Enfoque y la Idea son propuestos por Balakrishnan R (rbkraj000 GFG ID)