题目描述企业喜欢使用易记的电话号码。一种方式是用字母拼出单词例如TUT‑GLOP对应标准号码888‑4567。电话号码的标准形式为七位数字第333位和第444位之间有一个连字符如888‑1200。电话键盘上字母到数字的映射固定A,B,C→222D,E,F→333G,H,I→444J,K,L→555M,N,O→666P,R,S→777T,U,V→888W,X,Y→999Q和Z无映射。连字符可忽略。两个电话号码等价当且仅当它们转换成标准形式后相同。给定若干电话号码最多100000100000100000个要求找出所有出现次数超过111的号码按标准形式字典序升序输出并附出现次数若没有重复输出No duplicates.。输入格式第一行为数据组数随后有一个空行。每组数据第一行为一个正整数nnn表示电话号码个数。随后nnn行每行一个电话号码由数字、大写字母不含Q和Z和连字符组成其中恰好有777个字母或数字。每组数据之间有一个空行。输出格式对于每组数据按标准形式字典序升序输出所有出现次数大于111的号码每行格式为标准号码 次数。若没有重复输出No duplicates.。每组输出之间用一个空行分隔。样例输入1 12 4873279 ITS-EASY 888-4567 3-10-10-10 888-GLOP TUT-GLOP 967-11-11 310-GINO F101010 888-1200 -4-8-7-3-2-7-9- 487-3279样例输出310-1010 2 487-3279 4 888-4567 3题目分析每个输入字符串包含恰好777个有效字符数字或字母连字符可忽略。转换规则固定字母映射为数字数字不变忽略连字符和非法字符但输入保证有效。得到777位数字后按标准格式插入连字符输出。统计每个标准号码的出现次数只输出频次大于111的项并按数值升序排列。由于n≤100000n \le 100000n≤100000只需将每个号码转换为整数000到999999999999999999999排序后统计连续相同值的个数即可。解题思路实现步骤确定如下步骤1\texttt{1}1. 预定义字母到数字的映射表keypad[26]\textit{keypad}[26]keypad[26]其中Q和Z无映射但输入保证不含它们。步骤2\texttt{2}2. 对于每组数据读入nnn然后对每个电话号码字符串初始化整数t0t 0t0。遍历每个字符ccc若ccc为连字符则跳过若ccc为数字则tt×10(c−′0′)t t \times 10 (c - 0)tt×10(c−′0′)若ccc为字母则tt×10keypad[c−′A′]t t \times 10 \textit{keypad}[c - A]tt×10keypad[c−′A′]。由于输入保证恰好777个有效字符遍历结束后ttt即为777位标准号码的数值。步骤3\texttt{3}3. 将所有ttt存入数组dict\textit{dict}dict排序可使用sort\texttt{sort}sort代码中实现了快速排序。步骤4\texttt{4}4. 扫描排序后的数组统计连续相同的元素个数。若某个值出现次数大于111则将其转换为标准字符串输出前333位、连字符、后444位后跟空格和次数。若没有任何重复输出No duplicates.。步骤5\texttt{5}5. 每组数据之间输出一个空行。排序时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)空间O(n)O(n)O(n)满足n≤100000n \le 100000n≤100000的要求。代码实现// 487–3279// UVa ID: 755// Verdict: Accepted// Submission Date: 2017-12-02// UVa Run Time: 0.100s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intcmp(constvoid*a,constvoid*b){return(*(int*)a-*(int*)b);}voidquickSort(intdata[],intleft,intright){if(leftright){intpivotdata[(leftright)1];intileft-1,jright1;while(ij){doi;while(data[i]pivot);doj--;while(data[j]pivot);if(ij)swap(data[i],data[j]);}quickSort(data,left,i-1);quickSort(data,j1,right);}}inlinevoidnumber2string(intn,intc){intd[7]{0},k6;while(n0)d[k--]n%10,n/10;for(inti0;i3;i)coutd[i];cout-;for(inti3;i7;i)coutd[i];cout c\n;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intkeypad[26]{2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,0,7,7,8,8,8,9,9,9,0};intcases0,n,dict[100010];string telephone;cincases;for(intc1;ccases;c){if(c1)cout\n;cinn;for(inti0;in;i){cintelephone;intt0;for(autoc:telephone){if(c-)continue;t*10;if(isdigit(c))t(c-0);elsetkeypad[c-A];}dict[i]t;}//sort(dict, dict n);//qsort(dict, n, sizeof(int), cmp);quickSort(dict,0,n-1);booloutputedfalse;intcurrent-1,counter0;for(inti0;in;i){if(dict[i]current)counter;else{if(counter1){outputedtrue;number2string(current,counter);}currentdict[i];counter1;}}if(counter1){outputedtrue;number2string(current,counter);}if(!outputed)coutNo duplicates.\n;}return0;}总结本题通过将电话号码转换为整数利用排序统计重复次数避免了字符串直接比较和映射的复杂性。关键点在于正确实现字母到数字的映射并处理连字符的忽略。排序后扫描即可得到所有重复项。输出时注意标准格式前333位加连字符加后444位和字典序升序数值升序等价于字典序。该解法时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)空间O(n)O(n)O(n)适用于n≤100000n \le 100000n≤100000的大规模数据。