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?

思路1：

使用hash实现，这种方法不做赘述，实现如下：

1
2
3
4
5
6
7
8
9
10
def singleNumber(self, nums):
        dict = {}
        for i in range(len(nums)):
            if nums[i] not in dict:
                dict[nums[i]] = 1
            else:
                dict[nums[i]] += 1
        for single in dict:
            if dict[single] == 1:
                return single

思路2：

和Single Number类似的解法：

1.当数字num第一出现时：ones,twos = num, 0;
2.当其第二次出现时：ones,twos = 0, num;
3.第三次出现时：ones,twos = 0, 0，就相当于这个数字没有出现过，这样最后的结果就是ones了。

实现：

1
2
3
4
5
6
7
def singleNumber(self, nums):
        ones, twos = 0, 0
        for i in nums:
            ones = ones^i & ~twos
            twos = twos^i & ~ones

        return(ones)