JZ56 数组中只出现一次的两个数字

发表于 分类于 本文字数： 379 阅读时长 ≈ 1 分钟

JZ56 数组中只出现一次的两个数字

描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

数据范围：数组长度 $2≤n≤1000$，数组中每个数的大小$ 0<val≤1000000$
要求：空间复杂度 $O(1)$，时间复杂度 $O(n)$
提示：输出时按非降序排列。

示例1

1
2
3
输入：[1,4,1,6]
返回值：[4,6]
说明：返回的结果中较小的数排在前面

示例2

1
2
输入：[1,2,3,3,2,9]
返回值：[1,9]

题解

本题核心在于一点，a^b，若$a=b$则结果为0。我们将所有的数字逐个进行异或过后，得到的结果就是两个只出现过一次的数字的异或结果。而后再找出其最低的为1的位x，这个数位就是这两个数字最低的不同的数位。

再次进行异或遍历，此次根据x位是否为1分两组进行异或，最终两组的结果就是两个只出现过一次的数字，然后从小到大输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#
# @param nums int整型一维数组
# @return int整型一维数组
#
class Solution:
    def FindNumsAppearOnce(self, nums: List[int]) -> List[int]:
        xor_result = 0
        for num in nums:
            xor_result = xor_result ^ num
        diff_bit = xor_result & -xor_result
        a, b = 0, 0
        for num in nums:
            if num & diff_bit:
                a ^= num  # 该位为1的数字
            else:
                b ^= num  # 该位为0的数字
        return [a,b] if a < b else [b,a]