java - 使用 XOR 方法查找数组中缺失和重复的元素

Question

我正在练习数组的搜索算法。

我遇到过通过对包含从 1 到 n 的整数的给定元素数组使用 XOR 方法来查找缺失和重复元素的问题。 Find the missing and duplicate elements in an array in linear time and constant space 我非常能够理解我们如何获得 X 和 Y 的单独值(一个重复，另一个重复)

但是我无法理解我们如何能够确定哪些是重复的，哪些是重复的。

(根据给定的解决方案，我可以看到 XOR over list 的 xor 结果，其中有 set-bit 给出了缺失的元素，而其他列表给出了重复的元素)。 但是，我无法理解达成此决定的逻辑。

请帮助我理解这个决定背后的逻辑。

Answer 1

在进行异或运算时，如果数字出现偶数次，则异或为零，如果出现奇数次，则异或为该数。

偶数 5^5 或 3^3^3^3 的异或将为零。 奇数的异或 5^5^5^5^5=5 或 3^3^3=3 将是相同的数字。

如果仔细观察，您会发现找到重复项或同时缺少两者指的是同一件事。让我们举个例子来理解- 因为如果缺少某个数字，则意味着该数字的频率将为零，即偶数。 如果某个整数是重复的，则意味着该数字的频率将为偶数两次，每当您对同一数字进行偶数次 Xor 时，它都会导致零

Ex-考虑 dupArray(A)={1,2,3,5,5},missingArray(B)={1,2,3,4,_} 范围从 1 到 5 实际数组(C)={1,2,3,4,5}

A^C={5}

B^C={5}