剑指 Offer 56 - I. 数组中数字出现的次数_CodingPark编程公园数组中数字出现的次数

39 阅读 0 评论 26 点赞

我是靠谱客的博主酷酷星星，最近开发中收集的这篇文章主要介绍剑指 Offer 56 - I. 数组中数字出现的次数_CodingPark编程公园数组中数字出现的次数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

数组中数字出现的次数

问题

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：
2 <= nums.length <= 10000

链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

解答

Mine 方法1

时间复杂度空间复杂度上没有达到题目要求

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        dic = {}
        res = []
        for v in nums:
            if v in dic:
                res.remove(v)
            else:
                dic[v] = 1
                res.append(v)

        return res

在这里插入图片描述

Mine 方法2

时间复杂度空间复杂度上没有达到题目要求

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        dic = {}
        for v in nums:
            if v in dic:
                dic[v] += 1
            else:
                dic[v] = 1

        from operator import itemgetter

        c = sorted(dic.items(), key=itemgetter(1))

        return [i[0] for i in c[:2]]

在这里插入图片描述

Leetcode 引例

问题

如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？

解答

在这里插入图片描述

答案很简单：全员进行异或操作即可

考虑异或操作的性质：对于两个操作数的每一位，相同结果为
0，不同结果为 1。那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。

def singleNumber(nums):
    single_number = 0
    for num in nums:
        single_number = single_number ^ num
    return single_number


nums = [10, 10, 5, 9, 9, 90, 3, 90, 3]


print(singleNumber(nums))

Leetcode Offer 56答案

分组异或

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        ret = 0
        a, b = 0, 0
        for n in nums:
            ret = ret ^ n

        h = 1
        while(ret & h == 0):
            h = h << 1
        for n in nums:
            if (h & n == 0):
                a ^= n
            else:
                b ^= n
        return [a, b]

在这里插入图片描述

二刷时

出错❌
在这里插入图片描述

我们定位到 14行

在这里插入图片描述

错误原因：
我们可以看出，point&i ≠ 1 即 不是非0即1

结论：

可写成

for i in nums:
            if point&i:			# 注意看这里 也就是：有东西
                fin1 = fin1^i
            else:				# 				  没东西
                fin2 = fin2^i

完整代码

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        fin1 = 0
        fin2 = 0
        res = 0
        for i in nums:
            res = res ^ i
        
        point = 1
        while(point&res) == 0:
            point = point<<1
        
        for i in nums:
            if point&i:
                fin1 = fin1^i
            else:
                fin2 = fin2^i

        return [fin1, fin2]

也可写成

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        ret = 0
        a, b = 0, 0
        for n in nums:
            ret = ret ^ n

        h = 1
        while(ret & h == 0):
            h = h << 1
        for n in nums:
            if (h & n == 0):
                a ^= n
            else:
                b ^= n
        return [a, b]