数组中数字出现的次数

问题简述

数组 nums 中除一个数字只出现一次外，其他数字都出现了三次。找出那个只出现一次的数字。
要求：时间复杂度 O(N)，空间复杂度 O(1)

详细描述

在一个数组 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


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1

• 统计每个数字二进制各位出现的次数，然后对各位出现的次数对 3 求余，即可得到目标值的二进制各位的值；

• 因为每个数的二进制位数是固定的，所以空间复杂度依然是 O(1)；

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        
        cnt = [0] * 32

        for i in range(32):
            for x in nums:
                if x & (1 << i):
                    cnt[i] += 1
        
        ret = 0
        for i, n in enumerate(cnt):
            if n % 3:
                ret += 2 ** i
        
        return ret

优化：上述Python代码只能处理正数，如果是负数还要一步操作

数组中数字出现的次数 II（位运算 + 有限状态自动机，清晰图解） - Krahets

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        
        cnt = [0] * 32

        for i in range(32):
            for x in nums:
                if x & (1 << i):
                    cnt[i] += 1
        
        ret = 0
        for i, n in enumerate(cnt):
            if n % 3:
                ret += 2 ** i
        
        if cnt[31] % 3 == 0:  # 最高位是 0 为正数
            return ret
        else:
            return ~(ret ^ 0xffffffff)  # 这一步的操作实际上就是讲 ret 二进制表示中 32位以上的部分都置为 0

思路2：有限状态自动机

数组中数字出现的次数 II（位运算 + 有限状态自动机，清晰图解） - Krahets

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos = 0, 0
        for num in nums:
            ones = ones ^ num & ~twos
            twos = twos ^ num & ~ones
        return ones