c044 - 10008 - What's Cryptanalysis
題目描述
題目要求對輸入的文字進行頻率分析，統計每個字母（不區分大小寫）出現的次數，並按照出現次數從大到小，字母從小到大的順序輸出結果。
解題思路
使用一個大小為 26 的陣列 ans 來儲存每個字母的出現次數。遍歷輸入的每一行文字，將每個字母轉換為對應的索引（A-Z 為 0-25，a-z 為 0-25），並更新 ans 陣列中對應索引的值。
統計完所有字母的出現次數後，使用一個迴圈，每次找到 ans 陣列中最大值對應的字母，並輸出該字母及其出現次數。然後將該字母的出現次數設為 0，以便找到下一個最大值。重複此過程，直到 ans 陣列中所有元素都為 0。
複雜度分析
- 時間複雜度: O(N + M * K)，其中 N 是輸入的行數，M 是每行文字的平均長度，K 是字母表的長度 (26)。 統計頻率需要 O(N * M)，排序輸出需要 O(K * log K) 或 O(K) 取決於排序演算法。
- 空間複雜度: O(K)，其中 K 是字母表的長度 (26)。 空間複雜度主要來自於儲存字母頻率的
ans陣列。
程式碼
#include <iostream>
#include <string>
using namespace std;
int ans[26];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,max=0;
string a;
cin >> n;
getline(cin,a);
while(n--){
getline(cin,a);
for(int i=a.length()-1;i>=0;i--){
if(a[i]>='A'&&a[i]<='Z'){
ans[a[i]-65]++;
if(ans[a[i]-65]>max){
max=ans[a[i]-65];
}
}
else if(a[i]>='a'&&a[i]<='z'){
ans[a[i]-97]++;
if(ans[a[i]-97]>max){
max=ans[a[i]-97];
}
}
}
}
int maxn=0;
while(max!=0){
maxn=0;
for(int i=0;i<26;i++){
if(ans[i]==max){
char z='A'+i;
cout << z << " " << ans[i] << "\n";
ans[i]=0;
}
else if(ans[i]!=max&&ans[i]>maxn){
maxn=ans[i];
}
}
max=maxn;
}
}