041:找第一个只出现一次的字符

总时间限制: 1000ms 内存限制:65536kB

描述

给定一个只包含小写字母的字符串，请你找到第一个仅出现一次的字符。如果没有，输出no。

输入

一个字符串，长度小于100000。

输出

输出第一个仅出现一次的字符，若没有则输出no。

样例输入

abcabd
           

样例输出

c
           

思路：找第一个出现一次的字符->统计所有字符，每个出现的次数->遍历一遍，找出第一个次数为1的字符。

程序：

#include <iostream>
using namespace std;
#define Max 100000
typedef struct letterCount{
	char letter;//字符
	int count = 0;//出现的次数
}letterCount;
int main() {
	char s[Max]; //输入数据
	letterCount lc[Max];//把字符放在结构体中
	int lc_len = 0;//统计数组的长度
	cin.get(s,100000);
	for(int i = 0;i<100000;i++){//遍历输入的字符
		if(s[i]=='\0'){
			break;
		}else{
			int flag = 0;//标记是否之前统计过；0：没有，1：统计过
			for(int j = 0;j<lc_len;j++){//找这个字符之前是否出现过
				if(lc[j].letter==s[i]){//如果出现过，就在其次数+1
					flag = 1;
					lc[j].count++;
					break;//既然出现过了，就之前跳出循环，不用网下找了
				}
			}
			if(flag == 0){//没有出现过，就添加这个字符
				lc[lc_len++].letter = s[i];
				lc[lc_len-1].count++; 
			}
		}
	}
	int flag2 = 0;//0:没有出现过1次的，1：有
	for(int i = 0;i<lc_len;i++){//找只出现过一次的
		if(lc[i].count==1){
			flag2 = 1;
			cout <<lc[i].letter;
			break;
		}
	}
	if(flag2==0){
		cout << "no"<<endl;
	}
	return 0;
}
           

结果：通过。

分析：代码可以优化，而且效率为O(n^2)

优化（百度）后：只用一个数组，效率O(n^2)

程序：

#include <iostream>
#include <cstring>
using namespace std;
#define Max 100000
int main() {
	int length;
	char s[Max];
	cin.get(s,100000);
	length = strlen(s);
	int flag = 0;
	for(int i = 0;i<length;i++){
		flag = 0;//1:又出现了，0：没有 
		for(int j = 0;j<length;j++){
			if(s[i]==s[j] && i!=j){
				flag = 1;
				continue;
			}
		}
		if(flag == 0){
			cout <<s[i]<<endl;
			break;
		}
	}
	if(flag == 1){
		cout <<"no"<<endl;
	}
	return 0;
}
           

再次优化(百度)后：通过字符之差，来锁定该字符与其个数。效率O(n)

程序：

#include <iostream>
#include <cstring>
using namespace std;
#define Max 100000
void init(int count[],int len){
	for(int i = 0;i<len;i++){
		count[i] = 0;
	} 
}
int main() {
	char s[Max];
	int count[Max];//统计字符的个数,下标对应每个字符的值,数组中存放的为该字符的个数 
	init(count,Max);//初始化，每个字符的个数为0 
	cin.get(s,Max);
	int len = strlen(s);
	for(int i = 0;i<len;i++){
		count[s[i]-'\0'] ++;//字符与'\0'相差的值为该字符的下标，出现一次，个数+1
	}
	for(int i = 0;i<len;i++){//count数组元素为1,即该字符个数为1 
		if(count[s[i]-'\0']==1){//如果个数为1，则输出 
			cout<<s[i]<<endl; 
			return 0; 
		}
	}
	cout << "no"<<endl;//没有个数为1的 
	return 0;
}