Lessons4. Counting Elements - MissingInteger

MissingInteger - Find the smallest positive integer that does not occur in a given sequence.

문제요약

정수 배열 A에 나타나지 않는 가장 작은 양의 정수를 반환

Assume that:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [−1,000,000..1,000,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

A의 양의 정수들을 저장하고, 1부터 증가하면서 저장되지 않은 값을 찾는다.