[LeetCode] 268. Missing Number

268. Missing Number

LeetCode

https://leetcode.com/problems/missing-number/description/

Missing Number - LeetCode

 

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

0부터 n까지의 범위에 있는 n개의 서로 다른 숫자가 포함된 배열 nums가 주어졌을 때, 해당 범위에서 배열에 누락된 유일한 숫자를 반환하세요.

 

Example

Input: nums = [3,0,1]
Output: 2
Explanation:
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Input: nums = [0,1]
Output: 2
Explanation:
n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

---

1. 문제 요구사항 분석

배열에 없는 숫자 반환

무조건 한 숫자는 반환하게 되어있음. (size n까지의 숫자가 다 있어야함)

2. 접근 전략

😭 배열 정렬 후, for문 돌면서 index와 값이 다르면 return → 시간복잡도 O(n log n) : 정렬 시간

import java.util.*;

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++) {
            if (i != nums[i]) return i;
        }
        return nums.length;
    }
}

 

😁 가우스 공식 사용 → 시간복잡도 O(n)

1. 0부터 n까지 모든 숫자가 있다고 가정하고 가우스 공식으로 합 구함

2. 배열에 실제로 들어있는 숫자들을 모두 더하기

3. 1 - 2 해서 남은 숫자 return

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        
        // n이 매우 클 경우를 대비해 long 타입을 사용하여 오버플로우 방지
        long sumOfN = (long) n * (n + 1) / 2;
        
        long sumNums = 0;
        for (int num : nums) {
            sumNums += num;
        }
        
        // 결과값은 다시 int로 캐스팅하여 반환
        return (int) (sumOfN - sumNums);
    }
}