LeetCode - 268 부족 한 숫자

1. 제목 설명
0, 1, 2, n 의 n 개 수 를 포함 하 는 서열 을 정 하고 0. n 에 나타 나 지 않 은 그 수 를 찾 아 라.예시 1: 입력: [3, 0, 1] 출력: 2 예시 2: 입력: [9, 6, 4, 2, 3, 5, 7, 0, 1] 출력: 8 설명: 당신 의 알고리즘 은 선형 시간 복잡 도 를 가 져 야 합 니 다.당신 은 추가 상수 공간 만 사용 하여 실현 할 수 있 습 니까?
2. 문제 풀이 사고방식
해법 1: 비트 연산
분석 하 다.
이 또는 연산 (XOR) 은 결합 율 을 만족 시 키 고 한 수 를 두 번 똑 같은 이 또는 연산 을 하면 원래 의 수 를 얻 을 수 있 기 때문에 우 리 는 이 또는 연산 을 통 해 부족 한 숫자 를 찾 을 수 있다.
알고리즘
우 리 는 배열 에 n 개의 수가 있 고 부족 한 수 는] [0. n] 에 있다 는 것 을 안다.따라서 우 리 는 먼저 [0. n] 의 이 또는 값 을 얻 은 다음 에 결 과 를 배열 의 모든 수 에 대해 이 또는 연산 을 할 수 있다.빠 지지 않 은 수 는 [0. n] 과 배열 에서 각각 한 번 씩 나타 나 기 때문에 이 또는 후 0 을 얻 을 수 있다.그리고 부족 한 숫자 는 [0. n] 에서 한 번 만 나 타 났 고 배열 에서 나타 나 지 않 았 기 때문에 최종 적 인 차이 나 결 과 는 바로 이 부족 한 숫자 이다.
코드 를 작성 할 때 [0. n] 이 배열 의 아래 표 시 를 n 으로 표시 하기 때문에 다음 과 같은 모든 다른 연산 을 한 번 에 반복 해서 완성 할 수 있 습 니 다.
아래 표
0
1
2
3
숫자.
0
1
3
4
결과 의 초기 값 을 n 으로 설정 하고 배열 의 모든 수 와 그 아래 표 시 를 다른 연산 할 수 있 습 니 다. 즉,:
미 싱 = 러 브 (0 ∧ 0) 러 브 (1 ∧ 1) 러 브 (2 ∧ 3) 러 브 (3 ∧ 4) = (4 ∧ 4) 러 브 (0 ∧ 0) 러 브 (1 ∧ 1) 러 브 (3 ∧ 3) 러 브 2 = 0 󕝧 0 󕝧 2 = 2 로 빠 진 숫자 를 얻 었 다.

class Solution {
    public int missingNumber(int[] nums) {
        int missing = nums.length;
        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }
}

2.2 해법 2: 수학 방법
가우스 구 와 공식 을 이용 하여 [0. n] 의 합 을 구하 고 배열 의 모든 수의 합 을 빼 면 부족 한 숫자 를 얻 을 수 있다.

class Solution {
    public int missingNumber(int[] nums) {
        int expectedSum = nums.length*(nums.length + 1)/2;
        int actualSum = 0;
        for (int num : nums) actualSum += num;
        return expectedSum - actualSum;
    }
}

3. 링크 참조
https://leetcode-cn.com/problems/missing-number/solution/que-shi-shu-zi-by-leetcode/