UVa 499 What‘s The Frequency Kenneth
题目描述
题目要求统计每行文本中每个字母（大小写分别统计）出现的频率，并输出出现次数最多的字母（按先大写后小写的字母顺序排列），以及该频率。
输入格式
输入包含多行文本，每行可能包含任意可打印字符。输入以文件结束符（EOF\texttt{EOF}EOF）终止。
输出格式
对于每行输入，输出一行，包含出现频率最高的字母（按字母顺序，先大写后小写）以及该频率，格式如e 6或al 7。
样例
输入
When riding your bicycle backwards down a one-way street, if the wheel falls of a canoe, how many ball bearings does it take to fill up a water buffalo? Hello Howard.输出
e 6 al 7 a 3 Hlo 2题目分析
本题的核心是统计每行中字母的频率，并找出最高频率对应的字母集合。
算法步骤
- 初始化长度为525252的计数数组，索引0∼250 \sim 250∼25对应大写字母A∼Z\texttt{A} \sim \texttt{Z}A∼Z，索引26∼5126 \sim 5126∼51对应小写字母a∼z\texttt{a} \sim \texttt{z}a∼z。
- 遍历行中每个字符：
- 若为大写字母，对应索引ch−’A’\textit{ch} - \texttt{'A'}ch−’A’加111。
- 若为小写字母，对应索引ch−’a’+26\textit{ch} - \texttt{'a'} + 26ch−’a’+26加111。
- 找出计数数组的最大值maxFreq\textit{maxFreq}maxFreq。
- 遍历索引000到515151，若计数等于maxFreq\textit{maxFreq}maxFreq，则输出对应的字母。
- 输出空格和maxFreq\textit{maxFreq}maxFreq。
复杂度分析
每行字符处理一次，时间复杂度O(L)O(L)O(L)。
代码实现
// What's The Frequency, Kenneth?// UVa ID: 499// Verdict: Accepted// Submission Date: 2016-07-13// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);string line;while(getline(cin,line)){vector<int>counter(52);fill(counter.begin(),counter.end(),0);for(inti=0;i<line.length();i++)if(islower(line[i]))counter[line[i]-'a'+26]++;elseif(isupper(line[i]))counter[line[i]-'A']++;intmax_frequency=*max_element(counter.begin(),counter.end());for(inti=0;i<counter.size();i++)if(counter[i]==max_frequency)cout<<(char)((i<26?'A':'a')+(i<26?i:(i-26)));cout<<" "<<max_frequency<<endl;}return0;}