题目:
豆豆对数字的执着,让他在理科领域游刃有余,但他近乎疯狂的投入也使父母有些担心,为了让孩子能够全面发展,决定拓宽他的学习领域。正好家旁边有个绘画培训中心,父母就给豆豆报了名。学习绘画的第一天就让豆豆产生了浓厚的兴趣,还主动要求买了很多很多的画笔。画笔有多种颜色,豆豆有一个习惯就是同种颜色的画笔就买两支,一支备用,这样就总共攒了 N 支画笔(N 是偶数且 1<N<100000)。
可是数字的敏感无孔不入,豆豆脑里蹦出了一个奇怪的问题:如果蒙上眼任意拿走一支画笔,分析剩下的 N-1 支画笔就能找出拿走了哪种颜色,你能回答他吗?
输入格式:
第一行一个整数N(N 是偶数且 1<N<100000),表示剩下的画笔个数就是题目描述中的 N-1。
第二行 N-1 个用空格隔开的正整数 Ai(0<Ai<100000),表示剩下的画笔的颜色编号。
注意:数据保证有一个画笔的颜色编号出现了一次,其余的都出现了两次。
输出格式:
一个整数,表示拿走的画笔的颜色编号。
输入样例:
10
1 1 9 11 5 3 11 5 9
输出样例:
3
点睛:此题含义是在一组乱序数组里面,有多组相同的元素个数为2,只有一组数据的个数是1,本题需要将哪一个单独的数组查找出来。
解答:此题有两种算法。
法一:利用排序函数进行查找(因为sort函数只适用于C++,所以此法C语言不适用)
思路:
- 如何在不设置变量情况下,输入N?可以先开一个很大的数组,再进行变量输入。
- 此法核心在于如何在已经排序的数组里查询单个元素?因为元素已经排序完毕,相同的元素都是两个两个排序在一起,所以只需两个一查找,即在第二个for循环中i+=2非常重要!!!
法二:利用按位异或操作符(重点!!!也是最难理解的)
首先,我们需要先回顾一下^操作符的运算规则。
- 若两个数相同,则输出结果就是0,若两个数不同,输出结果就是1;
- 任何值与自身异或,结果为0
- 任何值与0异或,结果为其自身
- 交换律 a^b^c=b^a^c
- 结合律
我们了解之后,可以这样理解,我们在初始化数组内容后,都是两个相同为一组,只有一个落单,根据交换律,直接将两个相同放在一起,输出结果就是0;这时又根据任何值与0异或等于值本身,综上可以把落单的那一个直接输出。