昨天看了一道题
这道题要我们把单词排好序输出,每个单词后面跟上单词出现的顺序。
由于这段时间在学Go语言,所以我就用Go语言来做了,结果超时了,我当时的思路是这样的:
用一个map,存单词和出现次数,用slice存出现过的单词,输入完成后对vector进行排序,然后在将map里的内容输出,为此我还写了一个比较字符串的函数(有点蠢),这个方法,当然超时了。
之后我不服气,想着用c++再做一下试试,兴许c++性能强,就不会超(eee,这个想法也挺蠢的)结果还是超时,于是我就搜一下这个题,发现有人说c++里的map中的key是有序存放的,所以单词放进去就是按字典序排的,最后直接迭代就可以!!!!
所以我最后写出了这样的代码
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<map>
#include<stdio.h>
using namespace std;
int com(string a,string b){
int minlen = a.length()<b.length()? a.length():b.length();
int i;
for(i=0;i<minlen;i++){
if(a[i]!=b[i]){
return (int)(b[i]-a[i]);
}
}
return b.length()-a.length();
}
int main(){
int i,j;
int t;
cin>>t;
while(t--){
int n;
cin>>n;
map<string,int>mymap;
while(n--){
string str;
cin>>str;
mymap[str]++;
}
int nums=mymap.size();
printf("%d\n",nums);
map<string,int>::iterator iter;
for(iter = mymap.begin();iter!=mymap.end();iter++){
cout<<iter->first<<": "<<iter->second<<endl;
}
cout<<endl;
}
}
由此我又去探究了一下,发现,原来c++里的map相当于Java里的TreeMap,他们都是有序的而而c++中的hash_map和unordered_map是无序的。
Go语言中的map更怪了,遍历map的时候,它会使用随机数,所以你拿到的序列是随机的,要想用Go语言实现这道题的要求,可以转成切片,然后进行排序,不过呵呵,我用Go写没有AC。