LeetCode-Single-Number-I-II-III

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 6.8k | 阅读时长 ≈ 6 分钟
~~位运算，牛逼儿（破音~~ 等一下，Python牛逼儿

136. Single Number I

题目

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2
Input: [2,2,1]
Output: 1

Example 2:

1
2
Input: [4,1,2,1,2]
Output: 4

解

这道题要求是在O(n)时间下跑完算法，考虑到O(1)额外空间，基本就要考虑位运算之类的骚操作了，这题的思路就是两个相同的数在异或运算以后会等于0，那么就可以看作是所有出现两次的数互相异或，剩下的就是所求的数。以[4,1,3,2,1,2,3]为例：

1
2
3
4
5
6
7
4: 0100
1: 0001
3: 0011
2: 0010
1: 0001
2: 0010
3: 0011

可以一眼看出 0100 & 0001 & 0011 & 0010 & 0001 & 0010 & 0011 以后的结果为 0100

代码如下:

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

137. Single Number II

题目

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2
Input: [2,2,3,2]
Output: 3

Example 2:

1
2
Input: [0,1,0,1,0,1,99]
Output: 99

解

这题和之前那题乍看和前一题一样，但其实仔细一想并不是，只有在重复项出现偶数次，要找的那个数出现奇数次时，简单的异或运算才能发挥它的作用。这题实在是难到我了，翻开Discuss最高票回答看得头皮发麻似懂非懂，好在还有一位老哥给出了基于数字电路的解题思路，总的来说就是将之前一题的解题思路扩展，前一题异或之所以有效，是因为二进制下的异或操作会消去所有出现偶数次的0和1，那么对于重复项出现K次，要找的数出现M次情况，只需要设计一个类似于K进制的异或操作即可。

题目中重复项出现三次（也就是出现1，2，3次），对于三种情况，最少需要 $\biggl\lceil\log_{2}3\biggr\rceil=2$ 位来表示，对于1-bit的情况，可以得到如下真值表

当前位 下一位 结果位
a b c a’ b’
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 0 0

然后根据真值表写出逻辑表达式 $a = a\overline{b}\overline{c} + \overline{a}bc$， $b = \overline{a}b\overline{c} + \overline{a}\overline{b}c$，那么就可以得到相应的python式子啦

1
a, b = (a&~b&~c) | (~a&b&c), (a&~b&~c) | (~a&b&c)

32位int的情况在这里其实与1-bit没有什么差别（毕竟异或位运算是分开算的- -），接下来需要确定的是经过异或运算以后，需要返回的值是什么，这里原作者老哥貌似是理解错了题意，所以只给出了一个通解，Discuss最高票回答解释得更为详细一点。由于我们在表示三种情况时，用了ab来表示1、2、3次（比如出现一次为 01，a=0, b=1，出现两次为 10），所以根据题意，要找的那个数字只出现一次，所以只要返回b值即可，如果要找的数字出现两次，那么返回a值即可，如果要一个通解的话那么返回 a|b 也行，但这样的话多做一次位运算。

完整python代码如下

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a, b = 0, 0
        for c in nums:
            a, b = (a&~b&~c) | (~a&b&c), (~a&b&~c)|(~a&~b&c)
        return b

更优解

为了求得a和b，上面的逻辑表达式总共要进行14次位运算，其中有大量的计算显然是重复的，可以把b化简成 b1 = ~a & (b & ~c | ~b & c) = ~a & b ^ c 这样只需要三次位运算就可以得到b，然后再次通过真值表

a b b1 c a’ b’
1 0 0 0 1 0
0 1 0 1 1 0

可以得到 a = ~b1 & (a ^ c)

这样的话一共通过六次位运算就可以迭代一次ab的值，而且也没有增加额外的空间，更新后的python代码如下

1
2
3
4
5
6
7
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a, b = 0, 0
        for c in nums:
            b = b ^ c & ~a
            a = a ^ c & ~b
        return

LeetCode给出的结果是比之前的版本快个10%~20%左右

碎碎念

其实这里的通解算法要表达所有的k和p还是会有点问题的（设重复项出现k次，要求的数出现p次），那就是 $\biggl\lceil\log_{2}p\biggr\rceil>\biggl\lceil\log_{2}k\biggr\rceil$ 的时候,所选用的信息位不够表达所求数的出现次数情况

当然了其实对于很多数k，可以通过先约简的方法来做。但是对于一个比较大的质数，还是有一点讨论的余地的。

比如说k=113，p=199，要用7位来表示（a,b,c…)，虽然返回 a|b|c|... 必定会得到正确解，但是如果我们想省一点计算量（当p数值很大的时候其实还是有一丢丢丢优化的），这里的话因为p的值199超出了 $2^7$ 的表示范围，想要直接确定返回值会有一点点问题

这里的话处理方法其实也很简单，只需要把 p = p%k 即可，这样的话能保证p一定是比k小的，同时也不会影响到最后的结果（因为所有出现超过k次的数都会被k位异或操作清0）

260. Single Number III

题目

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

1
2
Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

解

这题的解法严格意义上来说与前面两题其实并不是同一个套路，但是思想上有一定的相似之处。把所有数字异或一遍，结果其实就是要求得的两个数的异或值，因为两个数是不同的，所以结果必然会有至少一位是1。对于这两个数来说（数字x,y），在这一位上x和y的取值有所不同，假设x在这一位上取0，y取1，那么对于其余的数字，必然有偶数个在这一位上取0，有偶数个在这一位上取1。把x与在这一位上取0的所有数字异或即可得到x，与此同理也可得到y

代码如下

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

虽然通过 xor &= -xor 的方式求这个mask值更加简短优雅一些，但我觉得从最低位一位一位往上移直到第一个1出现的搜索方法更加直观一些，而且两者并没有在LeetCode上表现出性能上的差别

更多情况

稍微扩展

加入两个数出现1次，其余数出现3次，那么也可以用第二题与第三题思路结合的方式来做，通过真值表写出表达式，b值就是两个数x与y三进制异或的结果，再通过第三题的思路，继续与mask位相同的其余数三进制异或，就可以得到x与y的

两个数出现2次，其余数出现3次的情况也类似，只要对a值做操作就可以了

求两个数出现两次，其余数出现三次的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def singleNumber(nums):
    a, b = 0, 0
    for c in nums:
        b = b ^ c & ~a
        a = a ^ c & ~b

    x, y = 0, 0
    xa, xb, ya, yb = 0, 0, 0, 0
    mask = 1
    while (a & mask == 0):
        mask = mask << 1

    for c in nums:
        if c & mask == 0:
            xb = xb ^ c & ~xa
            xa = xa ^ c & ~xb
        else:
            yb = yb ^ c & ~ya
            ya = ya ^ c & ~yb

    return [xa, ya]

if __name__ == '__main__':
    print(singleNumber([2,5,2,4,5,2,4,5,7,1,1,7,4]))

再进一步

假如两个数可以出现1次或2次，其余数出现3次，貌似也可以用第二题真值表的方法来写出表达式解题，但是这种情况下难以判断两个数具体的出现次数分布情况，可以说是很头皮发麻了。如果是三个数出现p次，情况会更复杂。更进一步，假设我们有N个数，其中n个数出现p次，N-n个数出现k次，还能够保持O(n)时间O(1)空间嘛？

Python救我

其实只要k和N-n保持一定的正比例关系，python还是可以做到的，稍微看了下第三题submission结果里别的解，居然还有类似这样的解，而且时间和空间开销都与位运算相似

1
2
3
4
5
6
7
8
class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        a= set(nums)
        a = sum(a)*3 - sum(nums)
        a = a/2
        return a

惊了，这些解乍一看会需要O(n)空间，然而其实并不用，回想一下其实python中的set设计是基于hashmap的, set(nums) 其实并没有加入O(n)空间（只是在nums的基础上加入了一些键），通过简单调用一下测试程序

1
2
3
4
5
6
7
8
9
10
from memory_profiler import *
import random

@profile(precision=4)
def test():
    a = [random.randint(1, 100) for _ in range(100000)]
    b = set(a)

if __name__ == '__main__':
    test()
# line Mem Usage Increment Line Contents
6 37.5430 MiB 0.9727 MiB a = [random.randint(1, 100) for _ in range(100000)]
7 37.5430 MiB 0.0000 MiB b = set(a)

可以看到在 b=set(a) 这边几乎是没有增加任何空间的，LeetCode上的提交结果在内存结果上也证实了这一点

那么如果能够用collection类里的Counter的话（Counter也是基于hashmap的），扩展情况就变得比较简单了，只需统计一下Counter，然后most_common一下就可以得到结果了

参考

https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers
https://leetcode.com/problems/single-number-ii/discuss/43296/An-General-Way-to-Handle-All-this-sort-of-questions.
https://leetcode.com/problems/single-number-iii/discuss/68900/Accepted-C%2B%2BJava-O(n)-time-O(1)-space-Easy-Solution-with-Detail-Explanations
https://leetcode.com/problems/single-number-iii/discuss/68931/Easy-Python-O(n)-O(1)-solution