本文写于2011-03-08

感谢mike，雪瑶姐，utd帮助我完成了这篇文章

题目：有n个数，其中绝大部分数出现了正好3次，只有一个数只出现了1次，请写一段程序把这个数找出来

解法1： 建一个hash table，把number作为key，遍历数组一遍，对出现过的数进行计数，最后再遍历一遍找到只出现一次的数。

空间复杂度:length(为了时间上高效，一般length要取到Theta(n))

时间复杂度： n^2/length+0.5n（n时间遍历一遍，每次要查找n/length的hash table,最后再遍历一遍）

解法2：对数组进行select，对小于pivot与大于pivot的数分别计数，对不能被3整除的一边进行递归调用。

 空间复杂度：如果不在乎源数据被改变是可以仅用O(1)的空间的，但通常来讲需要O(n)空间来备份

 时间复杂度：O(n)

解法3（感谢雪瑶姐提供）:

public static int findSpecial(int[] array){
int ones = 0;  //出现1次的1
int twos = 0; //出现2次的1
int not_threes;  //出现3次的1取反

for(int i :array){
twos |= ones & i; 
ones ^= i;
not_threes = ~(ones&twos);
ones &= not_threes;
twos &= not_threes;
}
return ones;
}
} 
 空间复杂度O(1),时间复杂度也是O(n),不会改变原数组，应该是最好的算法了

但是，这道题的讨论还没有完。假如把题目改成“有n个数，其中绝大部分数出现了正好2次，只有一个数出现了1次，请把这个数找出来” 有一个只需遍历一遍且不用额外空间的算法：把所有数字异或一遍，最后结果就是只出现1次的那个数。 那么，可能有人会想，在这道题的条件下，是不是也存在一个类似于异或的运算符#，可以仅把所有数#一遍以后就得到结果呢？、

答案是否定的。假如存在这个运算符#，那它必须满足下面这些条件：

 A={所有32位2进制数}  #:A->A
交换律 a#b=b#a
结合律 a#b#c=a#(b#c)
存在e 对于任意a a#e=a
对于任意a a#a#a=e

我们可以证明满足上面条件的运算符不存在：

首先我们定义一个负元-a：a#-a=e
由a#a#a=e 可知-a存在,根据结合律，-a=a#a (1)
假设-a不唯一,-a=b或c, 那么a#b#c=(a#b)#c=c=(a#c)#b=b（交换律&结合律）矛盾 (2)
由（1）（2）可知，-a存在且唯一。显然，-e=e
由交换律可知，如果a#b=e=>b#a=e，所以负元这个relation是可逆的, -a=b => -b=a
因为-e=e并且A是一个有限偶数项集合
所以必定还有一个数x，-x=x
那么x#x#x=e#x=x与题设里x#x#x=e矛盾

综上所述，这个运算符并不存在

感谢UTD同学在证明上的帮助