40 数组中只出现一次的数字

题目描述

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

解题思路

核心思想：利用异或运算的性质。

关键步骤：

1. 对所有数字异或，结果为两个只出现一次数字的异或值
2. 找到异或结果中任意一个为1的位
3. 根据该位将数组分为两组，每组的异或结果即为两个数字

时间复杂度：O(n) 空间复杂度：O(1)

Python 实现

def find_nums_appear_once(nums):
    """
    找出数组中只出现一次的两个数字

    Args:
        nums: 整型数组

    Returns:
        tuple: 两个只出现一次的数字
    """
    if not nums or len(nums) < 2:
        return ()

    # 1. 异或所有数字，得到两个只出现一次数字的异或结果
    xor_result = 0
    for num in nums:
        xor_result ^= num

    # 2. 找到异或结果中第一个为1的位
    mask = 1
    while xor_result & mask == 0:
        mask <<= 1

    # 3. 根据该位分组，分别异或
    num1, num2 = 0, 0
    for num in nums:
        if num & mask:
            num1 ^= num
        else:
            num2 ^= num

    return (num1, num2)


# 测试代码
if __xfile__ == "__main__":
    test_cases = [
        [1, 2, 3, 4, 5, 1, 2, 3],
        [2, 4, 3, 6, 3, 2, 5, 5],
        [1, 1, 2, 3],
    ]

    for nums in test_cases:
        result = find_nums_appear_once(nums)
        print(f"{nums} → 只出现一次的数字: {result}")

# 输出:
# [1, 2, 3, 4, 5, 1, 2, 3] → 只出现一次的数字: (4, 5)
# [2, 4, 3, 6, 3, 2, 5, 5] → 只出现一次的数字: (4, 6)
# [1, 1, 2, 3] → 只出现一次的数字: (2, 3)

图解

示例: [1,2,3,4,5,1,2,3]

步骤1: 异或所有数字
1^2^3^4^5^1^2^3 = (1^1)^(2^2)^(3^3)^4^5 = 4^5 = 1 (二进制: 001)

步骤2: 找第一个为1的位
mask = 1 (第一位为1)

步骤3: 分组
第一组（第一位为1）: 1, 1, 5
第二组（第一位为0）: 2, 2, 4, 3, 3

分别异或:
第一组: 1^1^5 = 5
第二组: 2^2^4^3^3 = 4

结果: (4, 5)

原理:
- 相同数字异或为0
- 0与任何数异或为该数本身
- 分组后，相同数字在同一组，异或后抵消
- 每组只剩下一个只出现一次的数字