当前位置:C++技术网 > 资讯 > 面试题:10 输入一个字符串,输出这个字符串中重复的元素及其个数

面试题:10 输入一个字符串,输出这个字符串中重复的元素及其个数

更新时间:2016-05-18 22:34:25浏览次数:1+次

编程实现:在一个字符串中,统计其中重复的字符的个数及输出该字符。
当要你实现的时候,你会怎么下手呢?一般来讲的话,我们就是利用数组及最常用的遍历。这些是最常用的解题思路。可是在面试的时候,面试官更希望看到的是亮点!你的解题过程不能太繁琐,最重要的是保证效率及复杂度。对于算法,如果我们学的不是web前端的话,STL是你需要会的。因为算法与STL关系很密切,不仅是算法,还有数据结构!而这个题目,我们也能够从STL入手来解决问题。
在STL中,有一个关联容器map,这个容器提供了一种算法find,及其本身的特性——pair。pair数据结构能够帮我们在存储数据的同时统计数量。而且,由于map容器是由红黑二叉树实作而成的,它具有自动排序的功能!这个要记住哦!
好了,下面我们来看看实现:

//输出字符串各个字符的个数
#include "iostream"
#include "windows.h"
#include "string"
#include "map"

using namespace std;

int main()
{
	string str;
	int len;
	char word;
	cin>>str;
	int index;
	map<char,int> counts;
	len=str.length();
	int i;

	for(i=0; i<len; i++)
	{
		word=str.at(i);
		++counts[word];//将输入的字符串中的字符挨个输入到map容器
	}
	for(i=0; i<len; i++)
	{
		char cha=str.at(i);
		map<char,int>::iterator num(counts.find(cha));//开始统计技术
		if(num==counts.end())
		{
			cout<<"查找出错!!!"<<endl;
		}
		if(num->second>1)//判断是否重复
		{
			index=str.find(cha,i+1);
			if(index!=str.npos&&i+1<len)
			{
				cout<<num->first<<" ";
				cout<<num->second<<endl;
			}
		}
	}
	system("pause");
	return 0;
}
在构造map时,传入char为数据,int为数量。这就为我们统计字符提供了方便。不过上面的代码只适合字符串中有两个重复字符的情况,若是大于两个,那么在输出的时候,就会重复了。后续改进算法......