e927 - pA. 字串排序

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一個只包含大寫字母的字串，並將字串中的字母按照字母順序（A 到 Z）排序後輸出。

解題思路

此題可以使用計數排序 (Counting Sort) 的概念來解決。由於輸入字串只包含大寫字母，我們可以建立一個大小為 27 的陣列 ans，用於記錄每個字母出現的次數。然後，遍歷輸入字串，統計每個字母的出現次數。最後，按照字母順序遍歷 ans 陣列，將每個字母輸出其對應的次數即可。getchar_unlocked() 和 putchar_unlocked() 函數用於提高輸入輸出的效率。

複雜度分析

• 時間複雜度: O(N + K)，其中 N 是字串長度，K 是字母的種類數 (本題為 26)。由於 K 是常數，因此時間複雜度可以簡化為 O(N)。
• 空間複雜度: O(K)，其中 K 是字母的種類數 (本題為 26)。

程式碼

#include <stdio.h>
int ans[27];
char a;
int main(){
	while(a=getchar_unlocked()){
		if(a<46)break;
		++ans[a-'A'];
	}
	for(int i=0;i<=26;++i)
		while(ans[i]--)
			putchar_unlocked(i+'A');
}