Sortieren Sie Zeichenfolgen nach dem ASCII-Wert des Zeichens

ASCII-Wert

ASCII (American Standard Code for Information Interchange) ist das gebräuchlichste Zeichenkodierungsformat für Textdaten auf Computern und im Internet. In standardmäßigen ASCII-codierten Daten haben 256 Buchstaben, Zahlen oder spezielle Zusatzzeichen und Steuercodes eindeutige Werte.

Problemstellung

Bei diesem Problem müssen wir nun die sortierte Zeichenfolge in aufsteigender Reihenfolge basierend auf dem ASCII-Wert des Zeichens finden, wobei die Zeichenfolge die Eingabe ist, die uns der Benutzer gibt. Mal sehen, wie wir dieses Problem lösen sollten.

Versuchen wir, dieses Problem anhand einiger Beispiele zu verstehen.

Eingabe - s = "$%7wjk()"

Ausgabe – „$%()7jkw“

Erklärung - Die ASCII-Werte der Zeichen der angegebenen Zeichenfolge lauten wie folgt -

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

Daher wird die Zeichenfolge in aufsteigender Reihenfolge der ASCII-Codewerte zu „$%()7jkw“

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

Ausgabe – „#)0fkmn“

Erklärung - Die ASCII-Werte der Zeichen der angegebenen Zeichenfolge lauten wie folgt -

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

Daher wird die Zeichenfolge in aufsteigender Reihenfolge der ASCII-Codewerte zu „#)0fkmn“

Erklärung des Problems

Lassen Sie uns versuchen, das Problem zu verstehen und eine Lösung zu finden. Wir wissen, dass die ASCII-Tabelle 256 Zeichen enthält, wobei jedes Zeichen einen eindeutigen Wert oder eine eindeutige Position hat. Unser grundlegendes Ziel ist es also, die Charaktere entsprechend zu sortieren. Wir können die integrierte Sortierfunktion verwenden, indem wir externe Funktionen verwenden, mit denen wir unser Ziel erreichen können. Ein anderer Ansatz besteht darin, einen Häufigkeitsvektor zu erstellen und die Häufigkeit jedes Zeichens in diesem Array zu speichern. Mit diesem Frequenzvektor und dem ASCII-Wert können wir die neue Zeichenfolge erhalten.

Lösung 1 Verwenden Sie den Frequenzvektor

Algorithmus

• Erstellen Sie einen Häufigkeitsvektor der Größe 256, da die Gesamtzahl der Zeichen in der ASCII-Tabelle 256 beträgt, und beginnen Sie den gesamten Vektor mit Null

• Führen Sie eine Schleife aus, um die Häufigkeit jedes Zeichens einer bestimmten Zeichenfolge zu speichern

• Definieren Sie nun einen zunächst leeren Ausgabestring

• Führen Sie eine weitere Schleife aus, um den Frequenzvektor zu durchlaufen, damit wir die Ausgabezeichenfolge erhalten können, indem wir die i-te Position Frequency_vector[i] umwandeln

• Gibt die Ausgabezeichenfolge als Endergebnis zurück

Beispiel

Das Folgende ist die C++-Programmimplementierung der oben genannten Methode:

#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;
}

Ausgabe

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

Komplexität des obigen Codes

• Zeitkomplexität – O(n); wobei n die Größe der Zeichenfolge ist. Hier beträgt die tatsächliche Zeitkomplexität O(n * 256), aber wir können sie als O(n) betrachten, da 256 als Konstante wie k betrachtet werden kann, während O(k * n) nur als O(n) betrachtet wird. .

• Platzkomplexität – O(256); denn der einzige zusätzliche Platz, der hier beansprucht wird, ist der Platz für das Frequenzarray, das eine Größe von 256 hat.

Lösung 2 Lösung mit integrierter Sortierfunktion

Algorithmus

• Definieren Sie eine externe Vergleichsfunktion, die in der Sortierfunktion zum Sortieren von Zeichen nach ASCII-Werten verwendet wird, dh um Zeichen zurückzugeben, deren int-Typkonvertierungswert kleiner als bei anderen Zeichen ist.

• Nutzen Sie nun die integrierte Sortierfunktion in der Hilfsfunktion und verwenden Sie einen zusätzlichen Parameter (Vergleichsfunktion), um die Reihenfolge korrekt zu erhalten.

• Rufen Sie die Hilfsfunktion auf und erhalten Sie die endgültige String-Ausgabe.

Beispiel

#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;
}

Ausgabe

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

Komplexität des obigen Codes

• Zeitliche Komplexität: O(log(n)); Wie wir alle wissen, benötigt die integrierte Sortierfunktion O(n * log(n)) Zeit, um den Code auszuführen. Bei dieser Methode verwenden wir die integrierte Sortierfunktion, indem wir eine zusätzliche Vergleichsfunktion verwenden, die die Zeichen basierend auf dieser Funktion sortiert.

• Raumkomplexität: O(1); Im obigen Code speichern wir keine Variablen in einer Datenstruktur.

Fazit

In diesem Artikel finden wir eine sortierte Zeichenfolge basierend auf dem ASCII-Wert der Zeichen in aufsteigender Reihenfolge. Wir können dieses Problem auf zwei Arten lösen. Zuerst können wir einen Häufigkeitsvektor der Größe 256 erstellen (die gleiche Anzahl von Zeichen in der ASCII-Tabelle) und alle Häufigkeiten jedes Zeichens speichern und dann von hinten iterieren, um die gewünschte Zeichenfolge zu erhalten. Eine andere Möglichkeit besteht darin, die integrierte Sortierfunktion mithilfe zusätzlicher Parameter zu verwenden, die in der Sortierfunktion übergeben werden.

Das obige ist der detaillierte Inhalt vonSortieren Sie Zeichenfolgen nach dem ASCII-Wert des Zeichens. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!