【LeetCode】137. Single Number II 解题报告（Python）

标签： LeetCode

---

题目地址：https://leetcode.com/problems/single-number-ii/description/

题目描述：

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?

题目大意

有一个数组，每个数字都出现了3次，除了其中的某一个只出现了1次。找出这个只出现了1次的数字。

解题方法

这个题本身不是很难，注意，不能使用异或运算搞定了。这个题的做法是把32位的二进制数进行遍历，统计每个数字的每一位出现的和。因为每个数字出现了3次或者1次，所以如果某一位出现的次数不是3次，那么这个位置一定是因为那个只出现1次的数字导致的。用来保存结果的res是0，因此使用或操作，就能把这个位置的数字变成1.

需要注意的是：python的整型方便是方便了，但是由于其没有最大值，所以，当输入是一堆负数的时候，会导致认为结果是个整数！因为32位有符号的被认为成了无符号的，所以这就是Python的一个坑。。

注意一下结论，以后出现位运算的时候，需要对结果进行判断一下最好。如果不在这个范围内，说明了结果被认为是无符号的数了，需要减去2 ^ 32。

16位整数中-32768到32767

32位整数中-2147483648到2147 483 647

最高位为符号位 ，请您计算2的15次方以及2的31次方，就可以得到以上结果

16位整数-2^15~215-1

32位整数-2^31~231-1

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for i in range(32):
            cnt = 0
            mask = 1 << i
            for num in nums:
                if num & mask:
                    cnt += 1
            if cnt % 3 == 1:
                res |= mask
        if res >= 2 ** 31:
            res -= 2 ** 32
        return res

日期

2018 年 3 月 14 日 --霍金去世日