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

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

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