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?
1 class Solution { 2 public: 3 int singleNumber(int A[], int n) { 4 int * record = new int[32]; 5 int ret = 0; 6 7 for (int i = 0; i < 32; ++i) { 8 record[i] = 0; 9 for (int j = 0; j < n; ++j) { 10 if ((A[j] >> i) & 1 == 1) { 11 ++record[i]; 12 } 13 } 14 if (record[i] % 3 == 1) { 15 ret |= (1 << i); 16 } 17 } 18 return ret; 19 } 20 };
与上一题Single Number相似的思路，用位运算来实现，不过不能直接用二进制的异或，而是记录每个bit上1出现的次数。所有出现过3次的数，各个为1的位也必定重复出现了3次。所以记录每个位上1出现的总次数，如果某位上1出现的次数不是3的倍数，那么该位上多出来的1是那个single number带来的。由此可以还原出所求的数字。无论该数出现1次还是2次或者4次，都可以找出来。
【Leetcode】Single Number II,布布扣,bubuko.com
原文：http://www.cnblogs.com/dengeven/p/3613444.html
