[LeetCode]Single Number II

问题变成了其他的数每个有三个。我们需要用更general的做法。我们可以统计每一位1的数量，然后对3取余，如果不为0，就说明target number的那一位是1。我们根据这对所有位验证即可，linear time，O(log n)的空间（说空间是O(32)是因为我们限制了input的大小，如果不限制的话就不是常数空间了），代码如下：

	class Solution {
	public:
	int singleNumber(vector<int>& nums) {
	vector<int> bits(32, 0);
	for(auto& num : nums)
	{
	for(int i = 0; i < 32; ++i)
	{
	if(num & (1 << i))
	++bits[i];
	}
	}
	int res = 0;
	for(int i = 0; i < 32; ++i)
	{
	if(bits[i] % 3)
	res |= (1 << i);
	}
	return res;
	}
	};

view raw Single Number II.cpp hosted with ❤ by GitHub