Интеллектуальное использование оператора XOR, чтобы найти недостающий номер

Question

Я столкнулся с следующей проблемой на LeetCode и попытался решить ее со следующим кодом, однако, кажется, даже лучшее решение, которое использует преимущество XOR.LeetCode имеет описание для решения XOR, однако я не могу понять его полностью.

Я просто не могу обернуть голову, почему нам нужно инициализировать пропущенную переменную с длиной массива, почему не инициализируйте его с нулем, и когда мы инициализируем его с нулем, почему не можетЭтот ал-файл находит пропущенный номер?Может кто-нибудь, пожалуйста, объясните это?

Ниже было мое решение, прежде чем я выучил, что Letcode предложил решение 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 $ , i.e., нам дают массив, содержащий один (отдельный) номер, взятый из 0, 1.

.
• Если заданный номер 0, то отсутствующий номер должен быть $ 1= 1 \ Land0 $ .
• Если данное число 1, то отсутствующий номер должен быть $ 0= 1 \ Land1 $ .

Для суммирования, если данное число равно $ a $ , то отсутствующий номер - это $ 1 \ a= n= n \ земля a \ not= 0 \ земля a $ .

---

Каковы фундаментальные причины этой магии в общем ситуациях?

Оказывается, Оператор BitteWise XOR, обычно обозначаемый « $ \ Land $ « На языках программирования, ведет себя как обычный оператор Plus.

.
• это коммутативно и ассоциативность . Таким образом, порядок операций вообще не имеет значения.
• $ 0 $ Функции как ноль, то есть $ a \ lax 0= A $ . Таким образом, $ 0 $ можно удалить.
• $ a \ land a= 0 $ Для каждого количества $ a $ . Так что, если один и тот же номер появляется дважды, они отменили друг друга.

вне языков программирования, побитовые xor чаще написаны как " $ \ oplus $ ", где символ плюс, " $ + $ " в центре напоминает нам, как она ведет себя как обычное дополнение.

Теперь рассмотрим выражение, $$ (0 \ oplus1 \ oplus2 \ oplus3 \ cdot \ oplus n) \ oplus (a_0 \ oplus a_1 \ aplus a_2 \ cdots \ oplus a_ { N-1}). $$ Всякий раз, когда есть пара того же номера, мы можем удалить их. Таким образом, все номера отменены между собой, за исключением того, что недостающий номер, поскольку этот недостающий номер является единственным номером, который появляется в $$ 0 \ oplus1 \ oplus2 \ oplus3 \ cdots \ oplus n $ $ но не в $$ a_0 \ oplus a_1 \ aplus a_2 \ cdot \ oplus a_ {n-1}. $$ Итак,

$$ (0 \ oplus1 \ oplus2 \ oplus3 \ cdot \ oplus2 \ roplus3 \ cdot \ 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 $ , $ \ cdots $ , $ N-1 $ с <класс Span= «Математический контейнер»> $ a_ {N-1} $ , оставляя только $ n $ непарным. Мы видим, что левая сторона $$ (0 \ oplus a_0) \ oplus (1 \ \ oplus a_1) \ oplus (2 \ oplus a_2) \ oplus \ cdot (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 \ cdot (n \ oplus a_ {n - 1})=text { Отсутствует номер} $$

На самом деле, нам не нужно делать сопряжение вообще. Мы даже можем предвкушать напрямую $$ f (n)= 0 \ oplus1 \ oplus2 \ oplus3 \ cdots \ oplus n =начать {случаи} N & \ Text {Если} n= 0 \ pmod4 \\ 1 & \ Text {Если} n= 1 \ pmod4 \\ N + 1 & \ Text {Если} n= 2 \ pmod4 \\ 0 & \ Text {Если} n= 3 \ pmod4 \\ \ end {случаи} $$ а затем вычислить $$ f (n) \ oplus a_0 \ oplus a_1 \ oplus a_2 \ cdot \ 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;
}

.

Приведенный выше подход очень похож на # 4 Формула Гаусса на летекоде .

Answer 2

Начните со списка любых n целых чисел.Дублируйте целые числа и рассчитайте XOR, если эти 2n целых чисел.Какой результат?Переставьте 2N целые числа каким-либо образом и рассчитать их хор.В чем результат.Удалите номер X из списка и рассчитайте XOR.Какой результат?Удалите другое число Y и рассчитайте XOR.Какой результат?

Теперь вернитесь к своей проблеме, и ответы, которые вы дали, прежде чем сказать вам сразу, что будет ваш результат.