一、题目

剑指 Offer 56 - I. 数组中数字出现的次数(位运算的妙用)

  1. 题目描述

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

示例1：

1
2
输入:  [4,1,4,6]
输出: [1,6]或者[6,1]

示例2：

1
2
输入:  [1,2,10,4,1,4,3,3]
输出: [2,10] 或 [10,2]

二、分析

1.方法1：排序后，暴力遍历

这种方法思路简单，但是时间复杂度较高。排序消耗O(nlogn),遍历消耗O(n)，思路简单，但是不是最优解。

2.方法2：位运算

分析

  1. 我们知道异或运算有个特点，0和任何数异或是任何数本身，先记住这个结论。我们先将此题简化为一个整型数组中只有一个数字$x$只出现了一次，其他数字$a_i$ 都出现了两次。数组定义如下$nums=[ a_i, a_i ,x]$对于这个简化了的题，我们如果想到用位运算异或的性质，就很好求解了，直接将数组中所有的数值做异或运算，结果就是出现了一次的数$x$。公式如下：

$$
x=a_i\quad xor\quad a_i\quad xor\quad x
$$

  1. 而这道题里面有两个数字$x,y$出现了一次。$nums=[ a_i ,a_i, x, y]$我们将其分隔为两部分$nums1,nums2$（如何分隔下面会细说），保证x,y分别在不同的部分中。然后转换为1.中将两部分用异或位运算就可以得到$x,y$。公式如下：
    $$
    x=a_i\quad xor\quad a_i\quad xor\quad x\
    y=a_k\quad xor\quad a_k\quad xor\quad y
    $$

    3.如何将$nums$ 分成$nums1和nums2$,同时还得保证$x\in nums1$ $y\in nums2$。我们知道x和y一定不相同，假设其二进制第n位不同，两者异或的结果在第n为一定为1。我们只需要找到改位置。然后拿$1<<n $ 去和$x,y$做与运算，根据结果0,1来将其分成两组。(两个运算结果一定一个为1，一个为0)

$$
1<<n\quad & \quad x\
1<<n\quad & \quad y
$$
至于其他存在两个重复的数分组也是用这种方法，只要保证相同的数分在同一组就行。$比如a1,a1在一组。a2,a2在一组$。

复杂度

  1. 时间：O(n):遍历 nums使用 O(n)时间，x⊕y 二进制位使用 O(32) = O(1)时间。
  2. 空间：O(1)

三、代码

1.方法1：排序后，暴力遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
'''
题目：剑指 Offer 56 - I. 数组中数字出现的次数
描述：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。
     请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
方法：排序后，暴力遍历
复杂度分析：时间：O(n^2):排序O(n^2)+遍历O(n)
            空间：O(1):res,i 
坑：异或运算，必须转换成二进制异或,然后求解。
比如4（100）xor 6(110)==2(010)
'''

@staticmethod
def singleNumbers(self, nums: List[int]) -> List[int]:
    nums.sort()
    res, i = [], 0
    while i < len(nums):
        if i == len(nums) - 1:
            res.append(nums[i])
            break
        if nums[i] == nums[i + 1]:
            i = i + 1
        else:
            res.append(nums[i])
        i = i + 1
    return res

2.方法2：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
题目：剑指 Offer 56 - I. 数组中数字出现的次数
描述：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。
     请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
方法：参考题解：位运算。通过全部异或得到(X xor Y)。在通过找到该结果第一个不同位m，通过m和nums
    依次与运算。进行分组，结果为0在一组，结果为1在另一组。以便唯一不同的X，Y分在两组中。（因为m & X 和 m&Y结果必然不同,利用
    该性质分组）
复杂度分析：时间：O(n):线性遍历 nums使用 O(N)时间，x⊕y 二进制位使用 O(32) = O(1)时间。
            空间：O(1)
坑：异或运算，必须转换成二进制异或。比如4（100）异或6(110)不是等于1而是等于2(010)
'''

@staticmethod
def singleNumbersA(self, nums: List[int]) -> List[int]:
    temp_res = res1 = res2 = 0
    m = 1
    # 将所有nums异或，结果为X ^ Y
    for i in nums:
        temp_res = temp_res ^ i
    # 找到X ^ Y 中第一个结果为1的位置。将该值与X,Y分别与运算，用于将X,Y分到不同组别
    # 分组后利用【只有一个唯一不同值的组内，全nums异或，可得到唯一不同值】性质，分别求出两个不同解
    while True:
        if m & temp_res == m:
            break
        else:
            m = m << 1
    for i in nums:
        if m & i == 0:  # 用于分组
            res1 = res1 ^ i  # 分组后利用【只有一个唯一不同值的组内，全nums异或，可得到唯一不同值】性质，分别求出两个不同解
        else:
            res2 = res2 ^ i
    return [res1, res2]

四、总结

这道题用位运算真是妙蛙种子吃着妙脆角秒进米奇妙妙屋秒到家了。

位运算常见性质总结:

1
2
3
4
5
6
7
0 or 任何数等于其本身
0 xor 任何数等于其本身（本题用到性质）
1 and 任何数等于其本身（本题用到性质）

0 and 任何数等于0
1 or 任何数等于1
1 xor 任何数等于本身取反