落单的数字

二级模拟题:落单的数字

题目描述

小图灵面前有n个数字 . ...，有的数字会重复出现。如果某个数字只出现了一次，则称它为"落单的数字”，来帮小图灵找出所有落单的数字吧。

输入描述

共两行，第一行一个整数n,第二行n个整数a1...@n 。

输出描述

一行，若干个整数,为所有落单的数字，按输入顺序输出，单个空格分隔。数据保证存在落单的数字。

样例1

输入

8

3 2 4 1 2 2 3 2

输出

41

提示

对于40%的数据:n<1000

对于100%的数据:1< n, a<10^5

思路：

  这道题我刚开始想的时候，用的是桶排序的思想，就是用另外一个数组sum来存，sum[a]++，a就是输入的其中一个数，++代表这个数的数量+1，之后进行循环遍历，如果sum[i]==1的话，那么就输出，是重复的。

代码：

#include
using namespace std;
int n,sum[100005]={0};
int main(){
	cin>>n;
	for(int i=0;i
		int a; 
		cin>>a;
		sum[a]++;
	}
	for(int i=0;i<=100005;i++)
	  if(sum[i]==1)
		cout<" ";
	return 0;
}

输出：

1 4

  诶，怎么不对，应该输出的是4 1啊，经过仔细阅读题目过后，我发现题目是按照输入先后来判断的，4是在1前面的不重复数字，所以应该先输入4，在输入1.

思路2：

  经过这次错误，我想了半天，想到了用结构体来进行，但是又觉得太麻烦了，想来想去，就觉得桶排序的思想更好。

  于是我想到了，把a设置为一个全局数组，不是一个局部变量，sum一样[a[i]]++，最后在判断的时候，也需要改变一下，循环遍历的时候判断sum[a[i]]是不是等于1，等于1就输出a[i]，这样将a设置为一个数组来进行桶的思想，是按照顺序来的，所以很实用。

#include
using namespace std;
int n,a[100005],sum[100005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	  if(sum[a[i]]==1)
		cout<" ";
	return 0;
}

  这是我昨天在有道小图灵进行的一个竞赛，等级分为1~3级，因为1级太简单了，我就从二级来先讲起。