智能使用XOR运算符查找缺失的号码

Question

我遇到了Leetcode上的以下问题，并尝试用以下代码解决它，但似乎有一个更好的解决方案，可以利用XOR。Leetcode对XOR解决方案有一个描述，但是我无法整体掌握它。

我只是无法围绕我的头包围，为什么我们需要初始化缺少的变量，与数组的长度，为什么不用零初始化它，当我们用零初始化时，为什么不能这个algo找到了缺少的号码？有人可以解释一下吗？

以下是我的解决方案在我学习的Leetcode之前，建议的XOR解决方案更好，更快

class Solution {
    public int missingNumber(int[] nums) {
        if(nums.length == 1)
            return nums[0] == 0 ? 1 : 0;

        int missing = 0;
        boolean tempNums[] = new boolean[nums.length+1]; //cuz one is missing

        for(int i:nums) {
            tempNums[i] = true;
        }

        for(int i=0; i<tempNums.length; i++)
            if(!tempNums[i]) {
                missing = i;
                break;
            }
        return missing;
    }
}

.

Answer 1

让我们使用更简单的示例来验证事实。

假设 $ n= 1 $ ，即，我们被给出一个包含从0,1的一个（独特）编号的数组。

• 如果给定的数字为0，则缺少的数字必须是 $ 1= 1 \ land0 $ 。
• 如果给定的数字为1，则缺少的数字必须是 $ 0= 1 \ land1 $ 。

总结，如果给定的数字是 $ a $ ，则缺少的号码是 $ 1 \ land a= n \ Land A \ not= 0 \ Land A $ 。

---

一般情况下这个魔法背后的根本原因是什么？

它掉出了按位XOR运算符，通常由“ $ \ land $ ”以编程语言表示，表现类似于普通加运算符。

• 它是换向和关联。所以行动顺序根本无关紧要。
• $ 0 $ 函数为零，即 $ a \ land 0= a $ 。所以 $ 0 $ 可以删除。
• $ a \ land a= 0 $ 为每个数字 $ a $ 。因此，如果相同的数字出现两次，则它们互相取消。

在编程语言之外，按位XOR更常写为“ $ \ oplus $ ”，其中plus符号“ $ + $ ”中央提醒我们，它表现得像普通的补充。

现在考虑表达式， $$（0 \ oplus1 \ oplus2 \ oplus3 \ cdots \ oplus n）\ oplus（a_0 \ oplus a_1 \ oplus a_2 \ cdots \ oplus a_ { n-1}）。 $$ 每当有一对相同的数字时，我们都可以删除它们。因此，所有数字都在彼此之间取消，除了缺少的号码，因为缺少的号码是 $$ 0 \ oplus1 \ oplus2 \ oplus3 \ cdots \ oplus n $的唯一数字$ 但不是 $$ a_0 \ oplus a_1 \ oplus a_2 \ cdots \ oplus a_ {n-1}。$$ so，

$$（0 \ oplus1 \ oplus2 \ oplus3 \ cdots \ oplus n）\ oplus（a_0 \ oplus a_1 \ oplus a_2 \ cdots \ oplus a_ {n-1}）= \文本{缺少的号码} $$

让我们在左侧更改“求和”的顺序。我们可以将 $ 0 $ 使用 $ a_0 $ ， $ 1 $ 使用 $ a_1 $ ， $ 2 $ 使用 $ a_2 $ ， $ \ cdots $ ， $ n-1 $ 与 $ a_ {n-1} $ ，只留下 $ n $ 未配对。我们看到左手侧是 $$（0 \ oplus a_0）\ oplus（1 \ oplus a_1）\ oplus（2 \ oplus a_2）\ oplus \ cdots（n-1 \ oplus a_ {n-1} ）\ oplus n。 $$ 现在，只需将 $ n $ 移动到表达式的前面。

---

“我只是无法围绕我的头包围为什么我们需要初始化缺少的变量，与数组的长度。为什么不用零初始化，当我们用零初始化时，为什么不能找到缺少的原因号码？“

与 $ n $ 初始化缺失变量，初始化丢失变量没有什么特别的特别之处。您肯定可以使用任何数字初始化，包括零。然后，应将剩余的数字配对 $ a_0，a_2，\ cdots，a_ {n-1} $ （任意< / em>，每个数字一次）。例如，我们有

$$ 0 \ oplus（1 \ oplus a_0）\ oplus（2 \ oplus a_1）\ oplus \ cdots（n \ oplus a_ {n-1}）=text {缺少的号码} $$

事实上，我们根本不必做配对。我们甚至可以直接预编译 $$ f（n）= 0 \ oplus1 \ oplus2 \ oplus3 \ cdots \ oplus n =begin {案例} n＆\ text {if} n= 0 \ pmod4 \\ 1＆\ text {if} n= 1 \ pmod4 \\ n + 1＆\ text {if} n= 2 \ pmod4 \\ 0＆\ text {if} n= 3 \ pmod4 \\ \结束{案例} $$ 然后计算 $$ f（n）\ oplus a_0 \ oplus a_1 \ oplus a_2 \ cdots \ oplus a_ {n-1}，$$ 这也会产生缺失的号码。因此，我们有以下更快的程序来计算缺失的号码。

public int missingNumber(int[] nums) {
    final int length = nums.length;
    // missing = length, 1, length + 1, 0 when length = 0, 1, 2, 3 mod 4.
    int missing = length % 2 == 0 ? length + (length / 2 % 2) : (length + 1) / 2 % 2;
    for (int i : nums) missing ^= i;

    return missing;
}

.

上述方法非常类似于方法Leetcode的＃4高斯公式。

Answer 2

从任何n个整数的列表开始。复制整数并计算XOR如果这2n整数。结果是什么？以任何方式重新排列2N整数并计算其XOR。结果是什么。从列表中删除数字X并计算XOR。结果是什么？删除另一个数字y并计算XOR。结果是什么？

现在回到您的问题，并在您之前给出的答案告诉您您的结果将是什么。