有一个数组为{"Liu Yi", "Chen Er", "Zhang San", "Chen Er", "Chen Er", "Li Si", "Li Si", "Wang Wu"}, 要求: (1)把数组中没重复的字符串按原先的先后顺序打印出来 (2)把数组中有重复的字符串,按出现次数从少到多的顺序打印出来,每个字符串只打印一次
C++中,vector按先后顺序存储数据,因此可把没重复的字符串按顺序存到vector中。 map默认是按key从小到大的顺序存放数据,所以可把有重复的数据存到map中,并且以出现次数为key,以字符串为value
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define len 8
// 计算某个字符串在数组中出现的次数
int countInArray(string s[], string element)
{
int cnt = 0;
for(int i = 0; i < len; i++)
{
if(element == s[i])
{
cnt++;
}
}
return cnt;
}
int main()
{
string s[len] = {"Liu Yi", "Chen Er", "Zhang San", "Chen Er", "Chen Er", "Li Si", "Li Si", "Wang Wu"};
vector<string> v;
map<int, string> m;
for(int i = 0; i < len; i++)
{
int count = countInArray(s, s[i]);
if(1 == count)
{
// 如果只出现一次,按先后顺序放到vector中
v.push_back(s[i]);
}
else
{
// 出现多次的,放到map中,以次数为key,字符串为value
m[count] = s[i];
}
}
// 把map中的字符串,按出现次数从少到多的顺序,加到vector中
map<int, string>::iterator mIt;
for(mIt = m.begin(); mIt != m.end(); mIt++)
{
v.push_back(mIt->second);
}
vector<string>::iterator vIt;
for(vIt = v.begin(); vIt != v.end(); vIt++)
{
cout << *vIt << endl;
}
return 0;
}
运行结果:
Liu Yi
Zhang San
Wang Wu
Li Si
Chen Er
这个算法的时间复杂度是n ^ n + 2 * n, 你有更好的方法吗?