LeetCode剑指Offer56-II:数组中数字出现的次数II

发表于 更新于 分类于 阅读次数： 本文字数： 658 阅读时长 ≈ 1 分钟

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

4.1 遍历

比较容易想到的思路是对数组排序后遍历数组，从索引1开始，如果当前元素和前一个元素相同，则索引指针往后跳三个，否则return前一个元素的值，当然考虑索引指针的边界情况。详见代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums = sorted(nums)
        i = 1
        while i <= len(nums):
            if nums[i] == nums[i-1] and i + 3 < len(nums):
                i = i + 3
                continue
            elif nums[i] == nums[i-1]:
                return nums[i+2]
            else:
                return nums[i-1]

4.2 进制位法

如下图所示，考虑数字的二进制形式。对于出现三次的数字，各二进制位出现的次数都是3的倍数。因此，统计所有数字的各二进制位中1的出现次数，并对3求余，结果则为只出现一次的数字。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = [0 for i in range(31)]
        for num in nums:
            for j in range(31):
                count[j] += num & 1
                num >>= 1
        ans = 0
        for k in range(31):
            ans <<= 1
            ans |= count[30-k] % 3
        return ans