1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「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