[LeetCode] 24.Missing Number

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

Missing Number - LeetCode

 

1. Problem

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.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

 

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.

 

Example 4:

Input: nums = [0]

Output: 1

Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1].

1 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.

2. Code

 

풀이(1) - sort해서 풀기

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;
    }
}

 

풀이(2) - 수학공식으로 풀기

public static int missingNumber(int[] nums) {
	    int resultSum = 0;
	    int arrSum = 0;
	    
		for(int i = 0; i < nums.length; i++) {
	    	 resultSum += i;
	    	 arrSum += nums[i];
	     }
		
		return resultSum + nums.length - arrSum;
}

 

3. Report

 이 문제는 0부터 주어진 배열의 크기까지의 숫자 중 배열에 존재 하지 않는 숫자를 고르는 것이다.

 

 처음엔 배열을 정렬한 후 0부터 배열크기까지 순차적으로 비교를 했다

배열 끝까지 찾지 못한 경우는 빠진 숫자는 nums.length이다.

 

 정렬하는 방법이 O(nlogn)걸리기 때문에 더 빠른 방법을 찾아 수학공식으로 풀었다.

 

 수학공식으로 푸는 법은  0부터 배열의 크기까지 모든 합에서 배열의 모든 합을 빼면 빠진 숫자가 나오는 것이다.

i는 0부터 nums.length-1까지 더해지기전에 마지막에 nums.length를 더한 값에서 배열의 합을 뺀다.