- 给定一个数组,这个数组中除了一个数出现一次,剩下的数都出现2次,找出这个数字。
要求:要求使用O(n)的时间复杂度,O(1)的空间复杂度。
思路:刚开始想到了排序,排序能达到的最佳也是O(nlogn)的时间复杂度,不符合要求。后来在别人的提示下,才想到了位运算。
A ^ 0 = A, A^A=0,A^A^B^B^C=C,所以设一个变量初始为0,与数组中的所有的数异或一遍,出现两次的数字异或为0,最后结果就是出现一次的数。
class Solution { public: int singleNumber(int A[], int n) { int result = 0; for (int i = 0; i < n; i++) { result ^= A[i]; } return result; } };
2.给定一个数组,这个数组中除了一个数出现一次,剩下的数都出现3次,找出这个数字。
要求:同1
思路:假定给定的四个数是1,1,1,2,他们是int类型,则对应的2进制为
00000001
00000001
00000001
00000010
则对应每一位1出现的个数对3求余,出现3次所得位的1全部消除,剩下的就是只出现一次的。
class Solution { public: int singleNumber(int A[], int n) { int i,j,result=0; int count[32]={0}; for(i=0; i<n; i++) { for(j=0; j<32; j++) { count[j] += (A[i]>>j)&1; count[j] %= 3; } } for(j=0; j<32; j++) { result += count[j]<<j; } return result; } };