按字元的ASCII值對字串進行排序

ASCII 值

ASCII（美國資訊交換標準代碼）是電腦和互聯網上文件資料最常見的字元編碼格式。在標準 ASCII 編碼資料中，256 個字母、數字或特殊附加字元和控制代碼都有唯一值。

問題陳述

現在，在這個問題中，我們需要根據字元的 ASCII 值按升序找到排序後的字串，其中該字串將是用戶給我們的輸入。讓我們看看應該如何解決這個問題。

讓我們嘗試借助一些範例來理解這個問題。

輸入 - s = "$%7wjk()"

輸出 - “$%()7jkw”

說明 - 給定字串的字元的 ASCII 值如下 -

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

因此，依照 ASCII 碼值的遞增順序，字串將變成「$%()7jkw」

輸入 - s = "#m 0f )nk"

輸出 - “#)0fkmn”

說明 - 給定字串的字元的 ASCII 值如下 -

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

因此，依照 ASCII 碼值的遞增順序，字串將變成「#)0fkmn」

問題解釋

讓我們嘗試了解問題並找到解決方案。我們知道 ASCII 表中有 256 個字符，其中每個字符都有唯一的值或位置。所以我們的基本目標是對字元進行對應的排序。我們可以透過使用可用於實現我們的目標的外部函數來使用內建排序函數。另一種方法是建立頻率向量並將每個字元的頻率儲存在該數組中。使用這個頻率向量和 ASCII 值，我們可以獲得新的字串。

解決方案 1 使用頻率向量

演算法

• 建立一個大小為 256 的頻率向量，因為 ASCII 表中的字元總數為 256，並以零開始整個向量

• 運行循環來儲存給定字串的每個字元的頻率

• #現在定義一個原本為空的輸出字串

• 運行另一個循環來遍歷頻率向量，因此我們可以透過對第 i 個位置Frequency_vector[i]進行類型轉換來獲得輸出字串

• 傳回輸出字串作為最終結果

範例

以下是上述方法的 C 程式實作：

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

輸出

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

上述程式碼的複雜性

• 時間複雜度 - O(n)；其中 n 是字串的大小。這裡，實際的時間複雜度是O(n * 256)，但我們可以將其視為O(n)，因為256 可以視為常數，例如k，而O(k * n) 僅視為O(n )。

• 空間複雜度 - O(256)；因為這裡唯一佔用的額外空間是頻率陣列的空間，其大小為256。

解決方案 2 使用內建排序功能的解決方案

演算法

• 定義一個外部比較函數，用於排序函數中，根據 ASCII 值對字元進行排序，即傳回 int 型別轉換值小於其他字元的字元。

• 現在，在輔助函數中使用內建排序函數並使用額外參數（比較函數）來正確取得順序。

• 呼叫輔助函數並取得最終的字串輸出。

範例

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

輸出

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

上述程式碼的複雜性

• 時間複雜度：O(log(n))；眾所周知，內建排序函數需要 O(n * log(n)) 時間來執行程式碼。在這種方法中，我們透過使用附加比較函數來使用內建排序函數，該比較函數將根據該函數對字元進行排序。

• 空間複雜度：O(1)；在上面的程式碼中，我們沒有在某些資料結構中儲存任何變數。

結論

在本文中，根據字元的 ASCII 值按升序查找排序後的字串。我們可以透過兩種方法來解決這個問題。首先，我們可以製作一個大小為256（與ASCII表中的字元數相同）的頻率向量，並儲存每個字元的所有頻率，然後從後面遍歷就可以得到所需的字串。另一種方法可以藉助內建排序函數，並藉助排序函數中傳遞的額外參數。

以上是按字元的ASCII值對字串進行排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！