[LeetCode]题解（python）：137-Single Number II

题目来源：

　　https://leetcode.com/problems/single-number-ii/

题意分析：

　　给定一个数组，数组里面每一个数字都出现了3次除了一个，找出那个数。要求时间复杂度O（n），空间复杂度O（1）。

题目思路：

　　把所有的数转化成32位的2进制。那么如果没有只出现一次的那个数，每个位的1的个数都是3的倍数，那么我们将所有位置上的数量都对3取余数，那么剩下的就是那个数的32位组成。

代码（python）：

class Solution(object):

    def singleNumber(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

        b,ans,count = [0 for i in range(32)],0,0

        i = 0

        while i < 32:

            for j in nums:

                if j < 0:

                    count += 1

                    j = -j

                if (j >> i)&1:

                    b[i] += 1

            ans |= (b[i] % 3) << i

            i += 1

        if count % 3 != 0:

            return -1*ans

        return ans

巴特西

[LeetCode]题解（python）：137-Single Number II

最新文章

热门文章