[LeetCode] 268. Missing Number

leetcode.com/problems/missing-number/

Missing Number - LeetCode

처음 풀이 방법

어차피 배열 내 값은 0부터 nums의 길이만큼 들어가기때문에, 정렬했을 때 i 값과 배열 요소가 다르면 해당 i 값이 missing number 이므로 리턴해 준 방법

 

배열 내 요소가 모두 i와 일치한다면?

n값 즉, nums.length 가 missing number이므로 미리 선언하고 리턴했다.

예) 범위가 0 ~ 3 일 때 (length = 3, n = 3)

배열 nums 가 [0,1,2] 라면, missing number = n = nums.length = 3

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

Approach 1: Sort 를 사용하므로 O(NlogN)의 시간복잡도

 

 

수학 공식을 이용한 풀이

가우스 공식 : 1부터 n까지 합계

n(n+1)/2

만약 n=3 이라면 원래 0 부터 3까지의 합은 0+1+2+3 = 6이다.

원래의 합계에서 배열 내 요소의 합을 빼주면, 빠진 숫자를 찾을 수 있다.

예) 배열 nums = [3,0,1] 이라면 6-4 = 2 가되어 빠진 값인 2를 리턴한다.

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

Approach 2 : for문을 한번 사용하고, nums 배열의 크기에 따라 시간이 증가하므로 O(N)의 시간복잡도