268. Missing Number

0부터 n까지의 연속된 정수 중에서 누락된 숫자를 찾는 문제입니다. 아래는 문제의 자세한 설명입니다:

문제 설명:

0부터 n까지의 연속된 정수 중에서 하나의 숫자가 빠져 있는 배열 nums가 주어집니다. 이 누락된 숫자를 찾아서 반환하세요.

예시:

Input: nums = [3, 0, 1]
Output: 2

배열 nums에서 0부터 3까지의 숫자 중 누락된 숫자는 2입니다.

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8

배열 nums에서 0부터 9까지의 숫자 중 누락된 숫자는 8입니다.

노트:

배열 nums에 중복된 숫자는 없습니다.
배열의 길이는 n입니다. (0부터 n까지의 연속된 정수가 모두 포함되어 있지만 하나가 누락됨)
이 문제를 해결하는 가장 간단한 방법은 0부터 n까지의 합과 주어진 배열 nums의 합을 비교하여 누락된 숫자를 찾는 것입니다. 0부터 n까지의 합은 등차수열의 합 공식을 사용하여 구할 수 있습니다.

 

public int MissingNumber(int[] nums) {
    int n = nums.Length;
    // 0부터 n까지의 합을 구함
    int expectedSum = (n * (n + 1)) / 2;
    // 배열 nums의 합을 구함
    int actualSum = 0;
    foreach (int num in nums) {
        actualSum += num;
    }
    // 누락된 숫자를 계산하여 반환
    return expectedSum - actualSum;
}

Array.Sort(nums): 주어진 배열 nums를 오름차순으로 정렬합니다. 이렇게 하면 배열의 원소들이 정렬된 순서로 나열됩니다.

small 변수를 0으로 초기화합니다. 

for 루프를 사용하여 배열 nums를 순회합니다. 루프 변수 i는 0부터 배열의 길이까지 증가합니다.

if (small + i != nums[i]): 현재 검사 중인 누락된 숫자의 예상값 small + i와 배열 nums에서 현재 위치 i에 있는 숫자 nums[i]를 비교합니다. 만약 이 두 값이 다르다면, small + i가 누락된 숫자입니다. 따라서 small + i를 반환하고 함수를 종료합니다.

만약 for 루프를 완료했는데도 누락된 숫자가 없다면, return nums[nums.Length-1]+1을 사용하여 배열에서 가장 큰 숫자에 1을 더한 값을 반환합니다. 
이렇게 함으로써 배열의 모든 숫자가 연속된 정수로 구성된 경우를 처리합니다.

이 코드는 배열을 정렬하고 순차적으로 숫자를 비교하여 누락된 숫자를 찾는 방식으로 작동합니다. 
코드의 시간복잡도는 배열을 정렬하는 시간에 의존하며, 누락된 숫자를 찾는 데는 O(n) 시간이 걸립니다.

public int MissingNumber(int[] nums) {
        Array.Sort(nums);
        int small = 0;
        for(int i= 0;i<nums.Length;i++){
            if(small+i != nums[i]){
                return small+i;
            }
        }
        return nums[nums.Length-1]+1;
    }