欠けた数を見つけるためのXOR演算子のインテリジェントな使用

Question

leestcodeで次の問題に出会い、次のコードでそれを解決しようとしましたが、XORを利用するさらに優れたソリューションがあるようです。LeetcodeはXORソリューションの説明がありますが、その全体が把握できません。

私の頭を包むことはできません。 でゼロでそれを初期化しないのはなぜゼロで初期化すると、なぜできないのですか。このアルゴは欠けていない番号を見つけますか？誰かがそれを説明してください？

次の解決策は、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から取得した1つの（異なる）番号を含む配列を与えられます。

• 与えられた数が0の場合、欠損数は $ 1= 1 \ land0 $ でなければなりません。
• 指定された数が1の場合、欠損数は $ 0= 1 \ land1 $ です。

要約すると、指定された番号が $ a $ の場合、欠損数は $ 1 \ land a= nです。 \ Land A \ Not= 0 \ Land A $ 。

---

一般的な状況でこの魔法の背後にある基本的な理由は何ですか？

プログラミング言語では、「 $ \ land $ で一般的に示されているビット単位のXOR演算子が表示され、通常のプラス演算子のように動作します。

• それは整換と連想です。だから操作の順序はまったく関係ありません。
• $ 0 $ はゼロとして、つまり $ a \ land 0= a $ 。 sa $ 0 $ 'は削除できます。
• $ A \ Land A= 0 $ すべての番号 $ a $ 。そのため、同じ数字が2回表示されている場合、それらは互いにキャンセルします。

プログラミング言語の外側では、ビット単位XORは一般的に「 $ \ oplus $ "として書かれています。ここで、プラスシンボル、 " $ + $ "は、通常の追加のように動作します。

現在、 $$（0 \ oplus1 \ oplus2 \ oplus3 \ 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}）=text {欠損番号} $$

左側の「合計」の順序を変更しましょう。 $ 0 $ を $ a_0 $ 、 $ 1 $ $ a_1 $ 、 で$ 2 $ $ A_2 $ 、 $ \ cdot $ 、 $ n-1 $ $ a_ {n-1} $ 、 $ n $ のみを残します。左側があることがわかります $$（0 \ Oplus A_0）\ Oplus（1 \ Oplus A_1）\ Oplus（2 \ Oplus A_2）\ Oplus \ CD（N-1 \ Oplus A_ {n-1} ）\ Oplus n。 $$ さて、 $ n $ を式の正面に移動するだけです。

---

"私たちが行方不明の変数を配列の長さで初期化する必要がある理由を周りに私の頭を折り返すことはできません。ゼロでそれを初期化しないのはなぜゼロで初期化すると、なぜこのアルゴが不足していないのはなぜ番号？ "

$ n $ を使用して、欠けている変数を初期化する特別なものは、配列の長さです。ゼロを含む任意の数字で確かに初期化することができます。次に、残り数字を $ a_0、a_2、¥{n-1} $ x （ ）とペアにする必要があります。 / 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 \\ \ end {ケース} $$ そして計算します $$ 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;
}

.

上記のアプローチは、アプローチと非常に似ています。 letercode の＃4 Gauss 'の式

Answer 2

n整数のリストから始まります。整数を複製し、これら2N整数の場合はXORを計算します。結果は何ですか？2N整数を任意の方法で並べ替えて、XORを計算します。結果は何ですか。リストから数字Xを削除してXORを計算します。結果は何ですか？別の数字を取り除き、XORを計算します。結果は何ですか？

今あなたの問題に戻り、あなたが与えた答えはあなたにあなたの結果が何になるのかをすぐにあなたに言う。