一、题目描述
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
- 思路
在线性时间内从一个数组中找到只出现一次的数（其他数都是出现两次），可以使用抑或运算，相同为0不同为1。
当出现偶数次的数抑或的结果为0
而出现奇数次的数抑或的结果为（如果是与0抑或运算）它本身
public class Solution {
public int singleNumber(int[] A) {
if(A == null)
return 0;
int k = 0;
for(int i=0; i<A.length; i++){
k = k ^ A[i];
}
return k;
}
}
二、题目描述（进阶）
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
第一版回顾
- 思路
求在不使用额外空间且时间复杂度为O(n)时，只出现一次的数（其他数都出现3次）
意味着标记等方法都不能用，首先想到的是二进制的位运算，在第一版中利用异或运算将出现2次的数消除，而出现1次的保留了下来，可以借鉴这样的思路。
首先转化为二进制表示，通过统计所有数每位二进制中1出现的次数，并对3取模，即可把出现3次的数全部消除且保留了出现1次的数，此时对应的二进制即为出现1次数的值。
例如{1，1，1，2}，变为二进制后对应的每位相加求1出现的个数，求得是1和3（从高位），再对每位统计对3取模，为1和0，此时表示的二进制10即为只出现1次的数2
以下为上述思路的实现，对于更优的位运算解法还需要学习！
public class Solution {
public int singleNumber(int[] A) {
if(A == null || A.length == 0)
return 0;
if(A.length == 1) //特殊情况需特判
return A[0];
int ans = 0;
for(int i=0; i<32; i++){ //int类型范围是32位二进制
int bitCnt = 0;
for(int j=0; j<A.length; j++){
bitCnt += ((A[j] >> i) & 1); //求每一位二进制对应1的个数
}
//将出现3次的数的影响消除
bitCnt %= 3;
//先左移i位到对应位数，再或运算求出当前对应的二进制数（或运算不影响之前统计的二进制表示）
ans = ans | (bitCnt << i);
}
return ans;
}
}
