a537 - 10789 - Prime Frequency
題目描述
題目要求計算輸入字串中每個字元的出現頻率，並找出頻率為質數的字元。輸出時，字元需按照 ASCII 值由小到大排列。若沒有字元的頻率為質數，則輸出 "empty"。
解題思路
首先，使用一個布林陣列 p 預先計算出 2 到 2000 之間的質數。接著，對於每個輸入字串，使用一個 map 來統計每個字元的出現頻率。然後，遍歷 map，檢查每個字元的頻率是否為質數（即 p[頻率] 是否為 0）。如果是質數，則將該字元添加到輸出結果中。最後，按照 ASCII 值排序輸出結果，如果沒有質數頻率的字元，則輸出 "empty"。
複雜度分析
- 時間複雜度: O(N + M)，其中 N 是輸入字串的總長度，M 是字串中不同字元的數量。預先計算質數的時間複雜度為 O(2000 log log 2000)，可以視為常數時間。統計頻率的時間複雜度為 O(N)，遍歷 map 的時間複雜度為 O(M)。
- 空間複雜度: O(2001 + M)，其中 2001 是質數陣列的大小，M 是字串中不同字元的數量。
程式碼
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(){
int p[2001]={1,1},con=1;
for(int i=2;i<=45;i++)
for(int j=i+i;j<2001;j+=i)
p[j]=1;
string a;
cin >> a;
while(cin >> a){
map <char,int> m;
bool d=0;
for(int i=a.length()-1;i>=0;i--)
m[a[i]]++;
cout << "Case " << con << ": ";
con++;
for(auto i=m.begin();i!=m.end();i++){
if(p[i -> second]==0){
cout << i -> first;
d=1;
}
}
if(d==0)cout << "empty";
cout << "\n";
}
}