[LeetCode] First Missing Positive

문제

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

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

Example 2:

Input: [3,4,-1,1] Output: 2

Example 3:

Input: [7,8,9,11,12] Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

 

Approach

메모리를 O(n)만큼 더 쓰면 map등을 사용해서 쉽게 풀겠지만

상수 크기만큼밖에 사용하지 못하므로 어려운 문제.

답은 Hash를 제시된 배열에 직접 구현하는 것이었다.

배열을 탐색하는 index를 i, 제시된 배열을 nums라 하면

우선 nums[i] 가 0보다 작거나 배열의 크기보다 크면 무시 -> missing number는 무조건 배열의 크기+1보다 작거나 같음

nums[i] != i일때

1. 이미 i번째 자리에 i+1이 존재 -> 무시

2. 그렇지 않으면 i+1을 i번째 자리로 옮기고 i번째 자리에 있던 자리는 i+1번째로 옮김 (자리바꾸기)

(무시된 숫자는 0으로 바꿈)

이렇게 제시된 배열에서 hash를 구현하며 배열을 탐색하고

다 탐색되면 다시한번 정리된 배열을 탐색해 i번째에 무시된 숫자(0)이 나오면 i+1이 missing positive이므로 i+1을 return

배열이 다 탐색되면 nums.size() + 1 을 return

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_FirstMissingPositive.cpp

chi3236/algorithm