資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究根據字元的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值，我們可以得到新的字串。
方法一：使用頻率向量
演算法
建立一個大小為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。
方法二：使用內建排序函式的解決方案
演算法
定義一個外部比較函式，該函式將用於排序函式中，以根據ASCII值對字元進行排序，即返回其int強制型別轉換值小於其他字元的字元。
現在，在輔助函式中使用內建排序函式，並使用一個額外的引數，即比較函式來正確獲取順序。
呼叫輔助函式並獲取最終的字串輸出。
示例
以下是上述方法在各種程式語言中的實現 −
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// Comparison Function to sort the string as per ASCII values of the characters
int comparison(const void* a, const void* b){
return (*(char*)a - *(char*)b);
}
// Function to sort the string as per ASCII values of the characters
void Helper(char* s){
size_t len = strlen(s);
qsort(s, len, sizeof(char), comparison);
}
int main(){
// Give input as a string by the user
char s[] = "$%7wjk()";
// Call Helper function to perform the sorting
Helper(s);
printf("The sorted string as per ASCII values of the characters is: %s", s);
return 0;
}
輸出
The sorted string as per ASCII values of the characters is: $%()7jkw
#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
# Comparison Function to sort the string as per ASCII values of the characters
def comparison(ch1, ch2):
return ord(ch1) <= ord(ch2)
# Function to sort the string as per ASCII values of the characters
def Helper(s):
# Sort the string s using the sorted() function and the custom comparison function
s = ''.join(sorted(s, key=lambda x: ord(x)))
return s
# Give input as a string by the user
s = "$%7wjk()"
# Call Helper function to perform the remaining tasks
print("The sorted string as per ASCII values of the characters is:", Helper(s))
輸出
The sorted string as per ASCII values of the characters is: $%()7jkw
上述程式碼的複雜度
時間複雜度 − O(n log n); 眾所周知，內建排序函式需要O(n * log(n))的時間來執行程式碼。在這個方法中，我們使用了一個額外的比較函式來使用內建排序函式，該函式將根據該函式對我們的字元進行排序。
空間複雜度 − O(1); 我們沒有在上述程式碼中將任何變數儲存在某些資料結構中。
結論
在本文中，為了根據字元的ASCII值按升序查詢排序後的字串。我們可以透過兩種方法解決這個問題。首先，我們可以建立一個大小為256（與ASCII表中的字元數相同）的頻率向量，並存儲每個字元的所有頻率，然後透過從後向前遍歷，我們可以得到所需的字串。另一種方法是在內建排序函式的幫助下，透過在排序函式中傳遞一個額外的引數來實現。
2K+ 次瀏覽
