小米2013校园招聘笔试题
小米2013校园招聘笔试题
题目：一个数组里，除了三个数是唯一出现的，其余的都出现偶数个，找出这三个数中的任一个。比如数组元素为【1, 2,4,5,6,4,2】，只有1,5,6这三个数字是唯一出现的，我们只需要输出1,5,6中的一个就行。
下面是我的思路：这个数组元素个数一定为奇数，而且那要求的三个数一定不可能每一bit位都相同，所以我们可以找到其中一个bit位不同，可以把那三个数字分出来，而且可以很推出三个数肯定可以分到两组不同的数组里面去，基于这样的思路就可以找出这三个不同的数字。
找到三个数字一个数的第一个bit位（这里是从右到左算）和其它二个不一样的数就行
如1,5,6的二进制分别为0001,0101,0110。因为6的的第一位为0，而其他的为1，用我的程序第一个输出的就是6了。程序如下：
01 #include
02 //得到第i位的二进制
03 #define isON(n, i) ((n) & 1
04
05 // Author: 397090770
06 // E-mail: [email protected]
07 // 转载请注明出处
08
09 void findTheSingleNumber(int *arr, int size){
10 int tempA = 0, tempB = 0;
11 int countA = 0, countB = 0;//用来计数用
12 int i = 0, j = 0;
13
14 for(i = 0; i
15 tempA = tempB = countA = countB = 0;
16 for(j = 0; j
17 if(isON(arr[j], i)){
18 tempA ^= arr[j];
19 countA++;
20 }else{
21 tempB ^= arr[j];
22 countB++;
23 }
24 }
25
26 if(countA & 0x1){//奇数
27 if(0 == tempB){
28 continue;
29 }else{
30 printf(
31 break;
32 }
33 }else{
34 if(0 == tempA){
35 continue;
36 }else{
37 printf(
38 break;
39 }
40 }
41 }
42
43 }
44
45 int main(){
46 int arr[] = {
47 /*1, 3, -9, 2, 1, 2, -10*/
48 1, 2,4,5,6,4,2
49 };
50
51 findTheSingleNumber(arr, sizeof(arr) / sizeof(arr[0]));
52 return 0;
53 }
时间复杂度为O(N)。输出为 6。（如果要全部输出不同的数，方法和上面的类似，这里就不给出了）
哪位大牛还有别的解法吗？
通过最新实战课程，系统学习hadoop2.x开发技能，在云帆教育，课程源于企业真实需求，最有实战价值，成为正式会员，可无限制在线学习全部教程；培训市场这么乱，云帆大数据值得你选择！！详情请加入QQ群：374152400，咨询课程顾问！
关注云帆教育微信公众号yfteach，第一时间获取公开课信息。