<Hard> First Missing Positive (LeetCode : C#)

https://leetcode.com/problems/first-missing-positive/

📕 문제 설명

정렬되지 않은 정수 배열이 주어질 때 없는 양의 정수 중 가장 작은 수를 반환

O(n) 내로 구현해야 하며 constant extra space 사용 가능

• Input
  정렬되지 않은 정수 배열
• Output
  배열에 없는 양의 정수 중 가장 작은 수

예제

풀이

nums 배열이 모두 양의 정수로 이루어진 케이스 vs 아닌 케이스를 고려하면 된다.

1. 새로운 nums 배열 길이만큼의 양의 정수 배열 생성
2. nums 배열 돌면서 해당 숫자가 nums 배열 길이보다 작은 숫자면 양의 정수 배열에 해당되는 위치에 넣기
3. 양의 정수 배열 돌면서 만약 비어있는 경우 바로 return
4. 끝까지 돈 경우 nums 배열 모두가 양의 정수로 앞에서 부터 다 채운 케이스이므로 길이 + 1 return

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int[] positiveIntNums = new int[nums.Length];

        foreach(int num in nums)
        {
            if (num > 0 && num <= nums.Length)
            {
                positiveIntNums[num - 1] = num; 
            }
        }

        for (int i = 0; i < positiveIntNums.Length; i++)
        {
            if (positiveIntNums[i] == 0)
            {
                return (i + 1);
            }
        }

        return nums.Length + 1;
    }
}

결과