东华研究生复试------23 只出现一次的数字

Karima ·

更新时间:2024-09-21

· 910 次阅读

问题描述 :

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

输入说明 :

所写的程序要求从标准输入设备中读入测试数据作为程序的输入数据。标准输入设备中有多组测试数据，每组测试数据占两行。第一行输入数据个数n，n大于等于1并且不超过100；第二行输入包含n个数字，除一个数字外，其余数字均出现两次，每个数字大小不超出int的范围。

输出说明 :

输出唯一出现一次的数字。注意：每组运算结果单独形成一行数据，每组测试数据与其后一组测试数据之间没有空行，第一组测试数据前面没有任何空行。

输入范例：
3
2 2 1
5
4 1 2 1 2

输出范例：
1
4

第一眼看着很简单，越看这道题实际上没那么简单，直接排序？也可以实现，排序完后，就是最后进行判断是不是只出现一次的时候，会有点乱，放弃了；然后，突然意识到这不就是基础题里面那个“选举投票”的翻版吗，这次求得是“票数为1”的值。

#include
#include
//从小到大进行排列
typedef struct{
	int num,fre;
}data;
int main(){
	int n,i,j,k,x;
	data *a;
	while(scanf("%d",&n)!=EOF){
		a=(data *)malloc(sizeof(data)*n);
		k=0;
		for(i=0;i<n;i++){
			scanf("%d",&x);
			for(j=0;j<k;j++){
				if(a[j].num==x){//之前已经出现过该值，频度加1
					a[j].fre++;
					break;
				}
			}
			if(j==k){//第一次出现该值，频度置为1
				a[k].num=x;
				a[k].fre=1;
				k++;
			}
		}
		for(j=0;j<k;j++){//输出频度为1的元素
			if(a[j].fre==1){
				printf("%d\n",a[j].num);
				break;
			}
		}
	}
	return 0;
}