LeetCode 136. 只出现一次的数字（易）& 面试题56 - II. 数组中数字出现的次数 II（中）

一个数组，其中N个数出现出现M次，其余数字出现Q次，求出出现M次的N个数字是哪些的题目，都要考虑用位运算来做。

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1: 

1
2
输入: [2,2,1]
输出: 1
示例 2: 
1
2
输入: [4,1,2,1,2]
输出: 4

直觉

哈希表，两次遍历。

第一次遍历，一张哈希表，存储映射关系。 第二次遍历，找到为1的数字。

时间复杂度： \(O(n \times 2)\) ，空间复杂度：\(O(1)\) 。

一次遍历

  • 遍历 nums 中的每一个元素。
    • 如果某个 nums 中的数字是新出现的，则将它添加到列表中。
    • 如果某个数字已经在列表中，删除它。

时间复杂度： \(O(n)\) ，空间复杂度：\(O(N)\) 。

对异或运算符的应用，非常有趣。

1
2
a = [2,3,2,4,4]
2 ^ 3 ^ 2 ^ 4 ^ 4 = 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3

时间复杂度： \(O(n)\) ，我们只需要将 nums 中的元素遍历一遍，所以时间复杂度就是 nums 中的元素个数，空间复杂度：\(O(1)\)

代码

哈希表，两次遍历。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hash_map = dict()
        for i in nums:
            if i in hash_map:
                hash_map[i] += 1
            else:
                hash_map[i] = 1
        
        for i in hash_map:
            if hash_map[i] == 1:
                return i

一次遍历

1
2
3
4
5
6
7
8
9
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        _list = list()
        for i in nums:
            if i in _list:
                _list.remove(i)
            else:
                _list.append(i)
        return _list[0]

对异或运算符的应用

1
2
3
4
5
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = nums[0]
        for i in range(1, len(nums)): res ^= nums[i]
        return res

举一反三

137. 只出现一次的数字 II（中）& 面试题56 - II. 数组中数字出现的次数 II（中）

Question

面试题56 - II. 数组中数字出现的次数 II

137. 只出现一次的数字 II（中）

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1: 

1
2
输入: [2,2,3,2]
输出: 3
示例 2: 
1
2
输入: [0,1,0,1,0,1,99]
输出: 99

Intuition

完全不用额外空间，非常难。但是可以做到使用常数级别的空间。

统计各个位上的数字

如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位出现的次数都是 \(3\) 的倍数。因此，统计所有数字的各二进制位中 \(1\) 的出现次数，并对 \(3\) 求余，结果则为只出现一次的数字。时间复杂度为 \(O(N)\)，空间复杂度为 \(O(1)\)。

137

参考链接

作者：Krahets 链接：https://leetcode-cn.com/problems/single-number-ii/solution/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

位运算

为了区分出现一次的数字和出现三次的数字，使用两个位掩码：seen_once 和 seen_twice。 思路是： 仅当 seen_twice 未变时，改变 seen_once。 仅当 seen_once 未变时，改变seen_twice。 时间复杂度为 \(O(N)\)，空间复杂度为 \(O(1)\)。

137_2

参考链接

作者：LeetCode 链接：https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetcode/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

  • Krahets
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counts = [0] * 32
        for num in nums:
            for j in range(32):
                counts[j] += num & 1
                num >>= 1
        res, m = 0, 3
        for i in range(32):
            res <<= 1
            res |= counts[31 - i] % m
        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)
  • LeetCode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen_once = seen_twice = 0
        
        for num in nums:
            # first appearance: 
            # add num to seen_once 
            # don't add to seen_twice because of presence in seen_once
            
            # second appearance: 
            # remove num from seen_once 
            # add num to seen_twice
            
            # third appearance: 
            # don't add to seen_once because of presence in seen_twice
            # remove num from seen_twice
            seen_once = ~seen_twice & (seen_once ^ num)
            seen_twice = ~seen_once & (seen_twice ^ num)

        return seen_once

260. 只出现一次的数字 III（中）

Question

260. 只出现一次的数字 III（中）

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

示例 :

1
2
输入: [1,2,1,3,2,5]
输出: [3,5]

注意：

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

Intuition

使用异或运算可以帮助我们消除出现两次的数字；我们计算 bitmask ^= x，则 bitmask 留下的就是出现奇数次的位。

260_1

x & (-x) 是保留位中最右边 1 ，且将其余的 1 设位 0 的方法。

260_2

算法 首先计算 bitmask ^= x，则 bitmask 不会保留出现两次数字的值，因为相同数字的异或值为 0。 但是 bitmask 会保留只出现一次的两个数字（x 和 y）之间的差异。

260_3我们可以直接从 bitmask 中提取 x 和 y 吗？不能，但是我们可以用 bitmask 作为标记来分离 x 和 y。我们通过 bitmask & (-bitmask) 保留 bitmask 最右边的 1，这个 1 要么来自 x，要么来自 y。

260_4

当我们找到了 x，那么 y = bitmask^x。 时间复杂度：\(O(N)\) 的时间遍历输入数组。 空间复杂度：\(O(1)\)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def singleNumber(self, nums: int) -> List[int]:
        bitmask = 0
        for num in nums:
            bitmask ^= num
        diff = bitmask & (-bitmask)

        x = 0
        for num in nums:
            if num & diff:
                x ^= num
        return [x, bitmask^x]

总结

一个数组，其中N个数出现出现M次，其余数字出现Q次，求出出现M次的N个数字是哪些的题目，都要考虑用位运算来做。