按字符的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中文网其他相关文章！