(Leet Code c++)Missing Number

268. Missing Number

 

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.

주어진 nums 벡터의 원소는 유니크하다.

그러기 때문에 nums.size() + 1의 bool형 벡터를 선언하고, 여기서 false인 수를 리턴하면 된다.

 

우선 nums.size()만큼 for문을 실행.

nums의 원소를 check에서 true로 바꿔준다.

 

for문이 끝나면 다시 check for문을 실행하여 빠진 수(false인 원소)를 바로 리턴하면 된다.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        vector<bool> check(nums.size() + 1, false);
        int len = nums.size();
        
        for(int i = 0; i < len; i++){
            check[nums[i]] = true;
        }
        
        for(int i = 0; i < check.size(); i++){
            if(!check[i]){
                return i;
            }
        }
        
        return 0;
    }
};