LeetCode-Python-260. 只出现一次的数字 III

72 阅读 0 评论 48 点赞

我是靠谱客的博主谨慎皮卡丘，这篇文章主要介绍LeetCode-Python-260. 只出现一次的数字 III，现在分享给大家，希望可以做个参考。

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]
注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

第一种思路:

开哈希表空间换时间，从而得到答案。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        dic = collections.defaultdict(int)
        
        for num in nums:
            dic[num] += 1
        
        return [key for key, val in dic.items() if val == 1]

复制代码

1
2
3
4
5
6
7
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return [key for key, val in collections.Counter(nums).items() if val == 1]

第二种思路：

学习自评论区，需要一点数学思维：

首先要知道一个数和它本身 XOR的结果是 0；一个数和0 XOR 的结果是它本身。

所以如果把整个数组的所有元素都XOR在一起，得到的结果= A ^ B ^ C ^ C ^ D ^ D（假设 A, B是只出现一次的元素, C, D是出现两次的元素） = A ^ B，

因为A ！= B，所以 A ^ B肯定不是0。

令 mask = A ^ B, 然后采用一个特殊的运算：

mask = mask & (-mask)，来找到mask不为0 的最后一位，

在这一位上，A和B肯定不同，所以这一位才不是0，

然后可以利用这个性质，把nums分成两个子数组，分别对应 & mask == 0 和 & mask == 1，

然后问题变成了，

两个相同的子问题：在一个数组里，只有一个元素出现了一次，其他元素都出现了两次，求这个元素的值。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        a, b = 0, 0
        mask = 0
        for num in nums:
            mask ^= num
        mask = mask & (-mask)
        
        for num in nums:
            if mask & num:
                a ^= num
            else:
                b ^= num
        return [a, b]