[LeetCode] Single Number II

Single Number II

Given an array of integers, every element appearsthreetimes except for one. Find that single one.

Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解题思路：

与Single Number不同，，这里不能再用异或操作来做了。可以为每个位上1的数目计数。然后将该计数%3，剩下的1肯定是单独的数字贡献的。

class Solution {public:int singleNumber(vector<int>& nums) {vector<int> bitNumCount(32, 0);int len = nums.size();for(int i=0; i<len; i++){int num = nums[i];for(int j = 0; j<32 && num!=0; j++){if(num & 0x1 == 1){bitNumCount[j]++;}num = num>>1;}}int result = 0;for(int i=31; i>=0; i–){result = result<<1;if(bitNumCount[i]%3!=0){result += 1;}}return result;}};上面用了一个32位的向量。经过优化，还可以更为精简：

class Solution {public:int singleNumber(vector<int>& nums) {int result = 0;int len = nums.size();for(int i=0; i<32; i++){int count = 0;for(int j=0; j<len; j++){count += (nums[j]>>i)&1;}result += (count%3)<<i;}return result;}};

不然你大概会一直好奇和不甘吧——