[LeetCode] 268. Missing Number

 

268. Missing NumberII

 

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

 

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.

 

🗝️ 최종 Answer

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
	let sortedNums = nums.sort((a, b) => a - b);
	let left = 0;
	let right = sortedNums.length-1;
    if (nums[right] == right) return right+1;

	while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] > mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

 

🎈Review

• 처음에 배열을 순서대로 sort 할 때 실수가 있었다.  nums.sort((a,b) => a-b) 대신에 그냥 nums.sort() 라고 해버린 것이다. 이렇게 되면 숫자가 아닌 문자열로 정렬하기 때문에 원하는 의도대로 정렬되지 않는다.
• 이걸 제외하고는 가볍게 binary search 로 풀면 된다.