99클럽 코테 스터디 29일차 TIL Missing Number

# 오늘의 학습 키워드 

이분탐색

 

# 오늘의 문제 

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

 

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.

 

Example 1:

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.

Example 2:

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.

Example 3:

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.

 

Constraints:

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

 

# 나의 풀이방식 

class Solution {
    public int missingNumber(int[] nums) {
        
        // 올림차순 정렬
        Arrays.sort(nums);

		// 배열에 들어갈수 있는 최대값이 됨
        int result = nums.length;
       
        // 0번 인덱스부터 차례로 돌다가 빠진 숫자 발견하면 return
        for(int i = 0; i < nums.length; i++){
            if( i != nums[i]){
                return i;
            }
        }

		// 최대값이 배열에서 빠져있는 경우
        return result;
    }
}

 

# 다른 사람 코드

0 ~ n 의 합에서 배열 원소의 합을 빼면 빠진 숫자가 나옴

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = (n*(n+1))/2;

        int currentSum = 0;
        
        for(int i : nums){
            currentSum+=i;
        }

        return expectedSum-currentSum;
    }
}