leetcode-137. Single Number II[很有意思的一道题目]

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?

题目链接:https://leetcode.com/problems/single-number-ii/

 

这道题目最直接的方法是使用哈希表来解决。

但是使用哈希表是文艺青年的做派。

对于追求极致的大牛来说,这显然还不够。

下面的解法思路是从其它大牛copy来的,简单分析一下:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        one, two, three = 0, 0, 0
        for v in nums:
            two |= one & v
            one ^= v
            three = ~(one & two)
            one &= three
            two &= three
        return one
思路解析:
因为除了一个出现了一次的数,其它数都重复了3次。我们可以想到用
位运算来解决问题。
我们用one记录当前位置之前(包括当前位置)所有数字的各个二进制位
的总数模3等于1 ,同样用two记录当前位置之前(包括当前位置)所有数
字的各个二进制位的总数模3等于2
比如当前数字是3,前面有1与4,那么one会记录3,1,4第1至32位bit
中1出现的次数模3==1的结果,two会记录模3==2的结果。
one&two的结果的某个比特位==1,说明one中的该比特位与two中的
该比特位都是1,那么说明该比特位出现了3次,需要从当前结果中消掉
这些比特位。很简单,one&two按位取反表明不需要去掉的比特位,
那么one&(~(one&two))将one中的出现3次的比特位去掉。
最后剩下只出现一次的数的所有的比特位都在one中记录。那么one肯定
就是那个只出现一次的数。