g006 - 密碼備忘錄 (Password)

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個包含大寫字母的字串，要求找出字串中出現次數最多的字母，並依序輸出所有出現次數最多的字母。如果所有字母都出現 0 次，則停止輸出。

解題思路

這題的核心是統計每個字母出現的次數，然後每次找出出現次數最多的字母並輸出。可以使用一個大小為 26 的陣列 ans 來儲存每個字母的出現次數，其中 ans[i] 儲存字母 'A' + i 的出現次數。

程式碼首先讀取輸入字串，然後遍歷字串，統計每個字母的出現次數。接著，進入一個迴圈，每次找出 ans 陣列中值最大的元素，並將對應的字母輸出。輸出後，將該字母的出現次數設為 0，以便下次迴圈中不會再次輸出。如果 ans 陣列中所有元素都為 0，則跳出迴圈。

複雜度分析

• 時間複雜度: O(N + KM)，其中 N 是輸入字串的長度，K 是字母的種類數 (26)，M 是出現次數最多的字母的數量。在最壞情況下，M 可能等於 N，因此時間複雜度可以簡化為 O(N + 26N) = O(N)。
• 空間複雜度: O(1)，因為 ans 陣列的大小是固定的 (26)，不隨輸入字串的長度而變化。

程式碼

#include <iostream>
using namespace std;
int ans[26];
string a;
int main(){
	cin >> a;
	for(int i=0;i<a.length();++i){
		++ans[a[i]-'A'];
	}
	while(1){
		int ma=0;
		string tmp;
		for(int i=0;i<26;++i){
			if(ans[i]>ma){
				tmp = 'A'+i;
				ma = ans[i];
			}
			else if(ans[i]==ma){
				tmp += 'A'+i;
			}
		}
		if(ma==0)break;
		for(int i=0;i<tmp.length();++i){
			ans[tmp[i]-'A']=0;
			cout << tmp[i];
		}
	} 
}