数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x 数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。

107 阅读 0 评论 71 点赞

我是靠谱客的博主长情大树，最近开发中收集的这篇文章主要介绍数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x 数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。

2013-09-07 19:57 1365人阅读评论(3) 收藏举报

 
分类：

算法（129）  
ACM/POJ/PAT/九度（129） 

 版权声明：本文为博主原创文章，未经博主允许不得转载。

数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。

这是@陈利人http://weibo.com/1915548291/A8jX24VyW#_rnd1378555193798出的一道题。

类似的：数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了两次。请给出最快的方法，找到x。

这道题是：数组A中，除了某一个数字x之外，其他数字都出现了两次，而x出现了一次。请给出最快的方法，找到x。的变种。

思路：http://blog.csdn.net/zhu_liangwei/article/details/11074997和这道题有些区别。

现在重新来看关于这几种题目，关键是找出一种多次出现对应位清零的技术。

异或运算是两次出现清零。

那么，三次出现清零呢？

在两次出现的基础上改进：如有已经两次出现了，如果再出现，让么算3次出现。

现在：

某一位偶数次出现1，使用even记录，对应为置为1；

某一位奇数次出现1，使用odd奇数，对应为置为1；

上一次某位偶数出现1，这次奇数出现1，说明是第三次，使用is_three，对应位清零。

具体代码：

[cpp] 
view plain
 copy


 print
?
 #include<stdio.h>  
 #include<stdlib.h>  
 int find_num(int *num,int len)  
 {  
     int i;  
     int even=0;  
     int odd=0;  
     for(i=0;i<len;i++){  
         even |= odd&num[i];//every postion which 1 appear is odd,1 is appear again,the count of 1 is even,set 1;  
         odd ^= num[i];//every postion,when the count of 1 is odd, the location of postion is set 1;  
         int is_three = (even&odd);//every postion,from even to odd , the 1 postion, 1 is appear three times;  
         int three_to_zero = ~is_three;//the postion which 1 is appear thhree time back to 0;  
         even &= three_to_zero;  
         odd &= three_to_zero;  
     }  
     return odd;//is need return only appear two time ,return even;  
 }  
 int main()  
 {  
    int num[]={8,8,8,1,1,1,3,4,3,3,5,5,7,5,7,7};   
    int x=find_num(num,sizeof(num)/sizeof(int));  
    printf("x=%dn",x);  
    return 0;  
 }  