基于XOR方法查找数组中缺失与重复元素的疑问

嘿，这个问题我当初刚学XOR找重复/缺失元素的时候也卡过！别担心，咱们一步步来解决它。

首先先确认下前提：你已经通过异或整个数组和1~n的所有数，得到了 xor_result = X ^ Y（X是重复元素，Y是缺失元素）。因为X≠Y，所以这个结果里至少有一个二进制位是1——这个位就是我们区分二者的关键。

第一步：找到X和Y不同的二进制位 #

我们先提取出xor_result最右侧的那个1，这个位代表X和Y在该位置上一个是0、一个是1：

# Python示例：获取最右侧的1
rightmost_set_bit = xor_result & -xor_result

原理是利用负数的补码特性：负数的补码是原数按位取反加1，和原数相与后会只保留最右侧的1。

第二步：分组异或得到X和Y #

接下来把原数组的所有元素、以及1~n的所有数字，分成两组：

• 第一组：该位为1的数
• 第二组：该位为0的数

分别对两组做异或操作，最终会得到两个数——就是我们要找的X和Y。现在问题来了：怎么判断哪个是重复的，哪个是缺失的？

这里有两种简单高效的方法：

方法一：遍历数组统计出现次数 #

遍历一次原数组，统计其中一个数（比如a）的出现次数：

• 如果出现2次，那a就是重复元素X，另一个数b就是缺失元素Y
• 如果出现0次，那b就是重复元素X，a就是缺失元素Y
  （注：正常情况下不会出现1次，因为原数组里X出现2次、Y出现0次，其余数都是1次）

示例代码：

def find_duplicate_and_missing(arr, n):
    xor_result = 0
    # 异或数组所有元素
    for num in arr:
        xor_result ^= num
    # 异或1~n所有数
    for num in range(1, n+1):
        xor_result ^= num
    
    # 找最右侧的1
    rightmost_bit = xor_result & -xor_result
    a, b = 0, 0
    
    # 分组异或数组元素
    for num in arr:
        if num & rightmost_bit:
            a ^= num
        else:
            b ^= num
    # 分组异或1~n的元素
    for num in range(1, n+1):
        if num & rightmost_bit:
            a ^= num
        else:
            b ^= num
    
    # 判断哪个是重复元素
    count_a = arr.count(a)
    return (a, b) if count_a == 2 else (b, a)

方法二：利用总和差验证 #

如果不想额外遍历数组统计次数，可以用总和差来判断：

• 计算原数组总和 sum_arr，以及1~n的总和 sum_n = n*(n+1)//2
• 我们知道 sum_arr = sum_n + X - Y（因为数组多了一个X，少了一个Y）
• 假设得到的两个数是a和b，若 a - b == sum_arr - sum_n，则a是X、b是Y；反之则b是X、a是Y

示例代码片段：

sum_arr = sum(arr)
sum_n = n*(n+1)//2
diff = sum_arr - sum_n

return (a, b) if (a - b) == diff else (b, a)

这个方法对大数组更友好，不需要额外的遍历统计。

核心逻辑总结 #

X和Y在我们选定的二进制位上取值不同，所以分组后会被分到不同组里。每组的异或操作会抵消掉出现两次的数（异或同一个数两次等于0），最终剩下的就是X和Y。再通过统计次数或总和差，就能轻松区分谁是重复元素、谁是缺失元素。

内容的提问来源于stack exchange，提问作者JeetToGeek