题目地址: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位整数-215~215-1

32位整数-231~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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发