Trier les chaînes par valeur ASCII du caractère

Valeur ASCII

ASCII (American Standard Code for Information Interchange) est le format de codage de caractères le plus courant pour les données texte sur les ordinateurs et sur Internet. Dans les données codées ASCII standard, 256 lettres, chiffres ou caractères spéciaux supplémentaires et codes de contrôle ont des valeurs uniques.

Énoncé du problème

Maintenant, dans ce problème, nous devons trouver la chaîne triée par ordre croissant en fonction de la valeur ASCII du caractère, où la chaîne sera l'entrée qui nous sera donnée par l'utilisateur. Voyons comment nous devrions résoudre ce problème.

Essayons de comprendre ce problème à l'aide de quelques exemples.

Entrée - s = "$%7wjk()"

Sortie - « $%()7jkw »

Explication - Les valeurs ASCII des caractères de la chaîne donnée sont les suivantes -

$ -> 36
% -> 37
( -> 40
) -> 41
7 -> 55
j -> 106
k -> 107
w -> 119

Ainsi, par ordre croissant des valeurs du code ASCII, la chaîne deviendra "$%()7jkw"

Entrez - s = "#m 0f )nk"

Sortie - « #)0fkmn »

Explication - Les valeurs ASCII des caractères de la chaîne donnée sont les suivantes -

(space) -> 32
# -> 35
) -> 41
0 -> 48
f -> 102
k -> 107
m -> 109
n -> 110

Ainsi, par ordre croissant des valeurs du code ASCII, la chaîne deviendra "#)0fkmn"

Explication du problème

Essayons de comprendre le problème et de trouver une solution. Nous savons qu'il y a 256 caractères dans la table ASCII, chacun ayant une valeur ou une position unique. Notre objectif fondamental est donc de trier les personnages en conséquence. Nous pouvons utiliser la fonction de tri intégrée en utilisant des fonctions externes qui peuvent être utilisées pour atteindre notre objectif. Une autre approche consiste à créer un vecteur de fréquence et à stocker la fréquence de chaque caractère dans ce tableau. En utilisant ce vecteur de fréquence et la valeur ASCII, nous pouvons obtenir la nouvelle chaîne.

Solution 1 Utiliser le vecteur de fréquence

Algorithme

• Créez un vecteur de fréquence de taille 256 car le nombre total de caractères dans la table ASCII est de 256 et commencez tout le vecteur par zéro

• Exécutez une boucle pour stocker la fréquence de chaque caractère d'une chaîne donnée

• Définissez maintenant une chaîne de sortie initialement vide

• Exécutez une autre boucle pour parcourir le vecteur de fréquence, afin que nous puissions obtenir la chaîne de sortie en transtypant la i-ème position Frequency_vector[i]

• Renvoyer la chaîne de sortie comme résultat final

Exemple

Voici l'implémentation du programme C++ de la méthode ci-dessus :

#include <bits/stdc++.h>
using namespace std;
// Function to Sort the string as per ASCII values of the characters
string Helper(string s){
    // Define the size of the given string
	int size = s.length();
	// Define a frequency vector of size 256, which is the same as the size of the characters as per the ASCII table, and initiate the value of the vector as 0
	vector<int> v(256, 0);
	// Run a loop to count the frequency of each character of the string
	for (int i = 0; i < size; i++) {
		v[s[i]]++;
	}	
	// Declare a string, initially empty, to find the final output
	string ans = "";
	// Run another loop to get the final output in accordance with the ASCII table
	for (int i = 0; i < 256; i++) {
		for (int j = 0; j < v[i]; j++)
		// Typecast the integer value to the character value to include it in the loop
			ans = ans + (char)i;
	}
	// Return the final output
	return ans;
}
int main(){
    // Give input as a string by the user
	string s = "$%7wjk()";
	// Call Helper function to perform the remaining tasks
	cout<< "The sorted string as per ASCII values of the characters is: " << Helper(s);
	return 0;
}

Sortie

The sorted string as per ASCII values of the characters is: $%()7jkw

Complexité du code ci-dessus

• Complexité temporelle - O(n); où n est la taille de la chaîne. Ici, la complexité temporelle réelle est O(n * 256), mais nous pouvons la considérer comme O(n) car 256 peut être considéré comme une constante comme k, tandis que O(k * n) n'est considéré que comme O(n ) .

• Complexité spatiale - O(256) ; car le seul espace supplémentaire occupé ici est l'espace pour le tableau de fréquences, qui a une taille de 256.

Solution 2 Solution utilisant la fonction de tri intégrée

Algorithme

• Définissez une fonction de comparaison externe, utilisée dans la fonction de tri pour trier les caractères en fonction des valeurs ASCII, c'est-à-dire renvoyer les caractères dont la valeur de conversion de type int est inférieure à celle des autres caractères.

• Utilisez maintenant la fonction de tri intégrée dans la fonction d'assistance et utilisez un paramètre supplémentaire (fonction de comparaison) pour obtenir la commande correctement.

• Appelez la fonction d'assistance et obtenez la sortie de chaîne finale.

Exemple

#include "bits/stdc++.h"
using namespace std;
// Comparison Function to sort the string as per ASCII values of the characters
bool comparison(char ch1, char ch2){ 
    return int(ch1) <= int(ch2);
}
// Function to sort the string as per ASCII values of the characters
string Helper(string s){
	// Sort the string s with the help of the inbuilt function sort()
	sort(s.begin(), s.end(), comparison);
	// Return the final output string s
	return s;
}
int main(){
    // Give input as a string by the user
	string s = "$%7wjk()";
	// Call Helper function to perform the remaining tasks
	cout<< "The sorted string as per ASCII values of the characters is: " << Helper(s);
	return 0;
}

Sortie

The sorted string as per ASCII values of the characters is: $%()7jkw

Complexité du code ci-dessus

• Complexité temporelle : O(log(n)); comme nous le savons tous, la fonction de tri intégrée prend du temps O(n * log(n)) pour exécuter le code. Dans cette méthode, nous utilisons la fonction de tri intégrée en utilisant une fonction de comparaison supplémentaire qui triera les caractères en fonction de cette fonction.

• Complexité spatiale : O(1); Dans le code ci-dessus, nous ne stockons aucune variable dans une structure de données.

Conclusion

Dans cet article, nous trouvons une chaîne triée en fonction de la valeur ASCII des caractères par ordre croissant. Nous pouvons résoudre ce problème de deux manières. Tout d'abord, nous pouvons créer un vecteur de fréquence de taille 256 (le même nombre de caractères dans la table ASCII) et stocker toutes les fréquences de chaque caractère, puis itérer par derrière pour obtenir la chaîne souhaitée. Une autre façon consiste à utiliser la fonction de tri intégrée, à l'aide de paramètres supplémentaires transmis dans la fonction de tri.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!