UVa 11577

題目

http://domen111.github.io/UVa-Easy-Viewer/?11577

給一個字串，求字串中的所有英文字母轉成小寫後，出現次數最多的有哪些

想法

用一個陣列 $cnt$ 儲存每個字母出現的次數，將 $cnt$ 中最大的值對應到的字母輸出

Code

#include<iostream>
using namespace std;
int cnt[26];
int n,px;
string s;
int main(){
	cin>>n;
	getchar();
	while(n--){
		int ans=0;
		for(int i=0 ; i<26 ; i++){
			cnt[i]=0;
		}
		getline(cin,s);
		for(int i=0 ; i<s.size() ; i++){
			if((s[i]>='A' && s[i]<='Z') || (s[i]>='a' && s[i]<='z')){
				px=tolower(s[i])-'a';
				cnt[px]++;
				ans=max(ans, cnt[px]);
			}
		}
		for(int i=0 ; i<26 ; i++){
			if(cnt[i]==ans){
				cout<<(char)('a'+i);
			}
		}
		cout<<'\n';
	}
	return 0;
}

時間複雜度分析

每筆測資會將整個字串看過一遍，時間複雜度為 $O(len(s))$

輸出的時間複雜度很小，可以直接視為 $O(1)$

每筆測資時間複雜度約為 $O(len(s))$