Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
題意：136的followup公浪，這次數(shù)組中出現(xiàn)的都是3次印蓖，求只出現(xiàn)一次的那個數(shù)盲泛。
思路：
這道題自己沒想到不用額外空間的方法蛋欣，看discuss有一種方法比較容易懂锨亏。
即這個數(shù)組每個數(shù)投射到一個int類型32位bit上，統(tǒng)計每一個bit位上的總個數(shù)闯捎。如果某個bit位上和數(shù)是3的倍數(shù)习劫，那么那個只出現(xiàn)一次的數(shù)肯定不會投射到這個bit位。最后把每個位上的和對3取余棒口，然后按位算出所求數(shù)字寄月。
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int res = 0;
for (int i = 0; i < 32; i++) {
int cnt = 0;
for (int num : nums) {
num = (num >> i) & 1;
cnt += num;
}
cnt %= 3;
res += cnt << i;
}
return res;
}