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

「LeetCode每日一题」—— LCOF.56 – I. 数组中数字出现的次数

flypython • • leetcode题解

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

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 27/04/2020 11:07
下一篇 » 30/04/2020 11:08

相关推荐