XOR 연산자의 지능형 사용은 누락 된 번호를 찾습니다

cs.stackexchange https://cs.stackexchange.com/questions/127360

문제

Leetcode에서 다음과 같은 문제를 해결하고 다음 코드로 해결하려고 시도했지만 XOR을 이용하는 더 나은 솔루션이있는 것 같습니다.Leetcode는 XOR 솔루션에 대한 설명을 가지고 있지만, 그 전체가 그것을 파악할 수는 없습니다.

배열의 길이로 누락 된 변수를 초기화 해야하는 이유, 을 초기화하지 않는 이유는 왜 & 0으로 초기화 할 때이를 초기화하지 않으려면 이유를 초기화 할 수 없습니다. 왜 할 수 없습니까?이 알고리는 누락 된 번호를 찾았습니까?누군가를 설명 해주십시오.

여기에 이미지 설명을 입력하십시오 >>

다음은 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;
    }
}
.

도움이 되었습니까?

해결책

우리가 단순한 예를 사용하여 사실을 확인하십시오.

$ n= 1 $ , 즉, 0, 1에서 찍은 하나의 숫자를 포함하는 배열이 주어집니다.

  • 주어진 숫자가 0이면 누락 된 번호는 $ 1= 1 \ land0 $ 이어야합니다.
  • 주어진 숫자가 1이면 누락 된 번호는 $ 0= 1 \ LAND1 $ 이어야합니다.

주어진 숫자가 $ a $ 이면 누락 된 숫자가 $ 1 \ Land A= n입니다. \ 땅 A \ NOT= 0 \ 땅 A $ .

일반적인 상황 에서이 마법의 근본적인 이유는 무엇입니까?

프로그래밍 언어에서 " $ \ land $ "에 의해 일반적으로 표시되는 비트 XOR 연산자가 일반적인 플러스 연산자처럼 작동합니다.

  • 은 전환 및 연관 이다. 따라서 운영의 순서가 전혀 중요하지 않습니다.
  • $ 0 $ 기능은 0으로, 즉 $ a \ land 0= a $ . 따라서 $ 0 $ 을 제거 할 수 있습니다.
  • $ a \ land a= 0 $ $ a $ 에 대해. 동일한 번호가 두 번 나타나면 서로 취소됩니다.

프로그래밍 언어의 외부에서, 비트 XOR는 더하기 기호 "> $ \ oplus $ "로 더 일반적으로 작성되었습니다. 센터의 컨테이너 "> $ + $ "우리에게 우리에게 알려줍니다.

이제 $$ (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}. $$ 그래서,

$$ (0 \ OPLUS1 \ OPLUS2 \ oplus3 \ codots \ 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 $ unpaired 만 남겨 둡니다. 우리는 왼쪽이 $$ (0 \ OLLUS A_0) \ OPLUS (1 \ OPLUS A_1) \ OPLUS (2 \ oplus a_2) \ oplus \ cdots (n-1 \ oplus a_ {n-1} ) \ oplus n. $$ 이제 $ n $ 을 표현식 앞쪽으로 이동하십시오.

"나는 방지를 배열의 길이로 누락 된 변수를 초기화 해야하는 이유를 포장 할 수 없습니다. 0으로 초기화하지 않는 이유는 0으로이를 초기화 할 때, 왜이 알고색은 누락을 찾을 수 없습니까? 번호? "

$ n $ , 배열의 길이로 누락 된 변수를 초기화하는 것에는 특별한 것은 없습니다. 0을 포함하여 모든 숫자로 확실히 초기화 할 수 있습니다. 그런 다음 $ 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 =시작 {사례} 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;
}
.

위의 접근법은 접근 방식과 매우 유사합니다. # 4 leeetcode

에 # 4 가우스의 공식

다른 팁

n 개의 정수 목록으로 시작합니다.정수를 복제 하고이 2N 정수가 있으면 XOR을 계산하십시오.결과는 무엇입니까?어떤 방식 으로든 2N 정수를 다시 정렬하고 XOR을 계산하십시오.결과는 무엇입니까?목록에서 숫자 x를 제거하고 XOR을 계산하십시오.결과는 무엇입니까?다른 숫자 Y를 제거하고 XOR을 계산하십시오.결과는 무엇입니까?

이제 문제로 돌아가서 즉시 결과가 될 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top