剑指 Offer 56 – II. 数组中数字出现的次数 II

题目描述

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：
输入：nums = [3,4,3,3]
输出：4

示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31

解题思路

方法一：哈希表
统计次数，次数为3就踢出哈希表。最后哈希表剩下的唯一一个值就是只出现一次的数字。
此处注意python和dict相关的语法：
判断num在不在dict的keys里：if num in d.keys()或if num in d
返回dict的第一个个key：num = [key for key in d.keys()][0]
删除dict的元素：num = d.pop(key)
方法二：位运算
这种办法复杂度不如方法一优秀。
将所有数的每一位加起来成为bit_sum，如果bit_sum不能被3整除，说明只出现一次的数字的此位为1。

解题代码

方法一：

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        d = dict()
        for num in nums:
            if num not in d:
                d[num] = 1
            else:
                d[num] += 1
                if d[num] == 3:
                    d.pop(num)
        return [key for key in d.keys()][0]

方法二：

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        result = 0
        bit_list = [0] * 32 # 最大都不到2^32
        length = len(nums)
        for i in range(32):
            bit_sum = 0
            bit = 1 << i
            for j in range(length):
                if nums[j] & bit != 0: # 判断这一位是不是1，是的话加起来
                    bit_sum += 1
            if bit_sum % 3 == 1: # 如果bit_sum不是3的倍数的话，说明有个只出现一次的数字的此位为1
                result += 2 ** i
        return result

执行结果

执行用时：44 ms, 在所有 Python3 提交中击败了91.39%的用户
内存消耗：16.1 MB, 在所有 Python3 提交中击败了16.92%的用户