「LeetCode每日一题」—— LCOF.56 – I. 数组中数字出现的次数
LCOF.56 - I. 数组中数字出现的次数
链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
难度:中等
题目
点击原文链接跳转查看题目
思路
这个题是找数组中出现一次数字的变型,数组中有两个只出现一次的数字,而且要求时间复杂度是O(n),空间复杂度是O(1)。
我们可以先忽略复杂度要求限制,那其实就是对数字进行计数。找到两个只出现一次的数字即可,但是这里使用了额外的数据结构,不满足空间复杂度的要求。代码见计数方案。
现在我们考虑要满足复杂度要求,找到只出现一次数字时,可以用异或,那这里也可以使用异或,只是要做成分组异或。
分组异或就是把数字分成两组,需要把相同的数组分到同一组,两个数字分到不同的组。那么应该怎么做呢
先把所有的数字异或,得到的就是两个不同数字的异或值,因为这两个值的二进制位肯定不相同,那异或结果中为1的那一位肯定是不相同的。 这个不同,可以让我们得到一个mask值(不同的位为1,其他位为0),最后所有数字与这个mask值与,通过结果来区分两个数字。代码见分组异或。
方案代码
分组异或:
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
ret = functools.reduce(lambda x, y: x ^ y, nums)
div = 1
while div & ret == 0:
div <<= 1
a, b = 0, 0
for n in nums:
if n & div:
a ^= n
else:
b ^= n
return [a, b]
计数方案:
from collections import Counter
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
res = []
d = Counter(nums)
for key,value in d.items():
if value == 1:
res.append(key)
if len(res) == 2:
return res
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/358.html
您必须登录才能发表评论。