First Missing Positive

어려움배열과 문자열 해싱

+10

정렬되지 않은 정수 배열 nums가 주어집니다. nums에 나타나지 않는 가장 작은 양의 정수(1 이상)를 반환하세요. 배열에는 음수, 0, 중복된 값, 배열의 길이보다 훨씬 큰 값이 포함될 수 있습니다.

함수

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: 정렬되지 않은 정수들로, 중복될 수 있으며 음수, 0 또는 매우 큰 수일 수 있습니다
반환값integer: nums에서 누락된 가장 작은 양의 정수

제약 조건

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
값은 특정한 순서가 없으며 반복될 수 있습니다.

예제

입력: nums = [5, -2, 1, 3, 2, 9]
출력: 4
설명: 1, 2, 3은 모두 배열에 있고 4는 없으므로 답은 4입니다. 더 작은 값이 하나라도 빠져 있으면 5와 9는 중요하지 않습니다.

후속 질문

O(n) 시간 안에, 추가 메모리는 O(1)만 사용하면서 답을 찾을 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

정렬에는 O(n log n)의 시간이 걸리고 해시 집합에는 O(n)의 추가 메모리가 필요합니다. 상한을 이용하면 둘 다 피할 수 있습니다. n개의 값은 1부터 n+1까지의 수 중 최대 n개만 포함하므로, 답은 최대 n+1입니다. 1부터 n까지의 값만 중요하며, 배열에는 이를 기록할 n개의 슬롯이 있으므로 추가 메모리는 O(1)로 줄어듭니다.

각 후보를 전체 스캔으로 시도하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

후보 1, 2, 3, ...을 순서대로 테스트합니다. 각 후보에 대해 배열 전체를 훑고, 훑는 동안 찾지 못한 첫 번째 후보를 반환합니다. 상한에 따라 n+1을 넘어서 테스트하는 일은 없습니다.

배열에 1부터 n까지의 값이 들어 있으면, 평균적으로 각 후보는 배열의 절반쯤 훑었을 때 발견되므로 n = 10^4일 때 비용은 약 n²/2 = 5 × 10^7회의 비교입니다.

알고리즘

candidate를 1로 설정합니다.
nums에서 candidate와 같은 요소를 처음 찾을 때까지 검색합니다.
일치하는 요소가 없으면 candidate를 반환합니다.
그렇지 않으면 candidate에 1을 더하고 다시 검색합니다. n+1을 넘지 않습니다.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

플래그 배열에서 1부터 n까지의 값을 표시합니다

핵심 아이디어

정답은 최대 n+1이므로 1보다 작거나 n보다 큰 값은 건너뜁니다. 길이가 n+1인 불리언 배열 present에 나머지 값을 기록하므로 10^9 같은 값은 저장되지 않습니다. 플래그가 false인 1부터 n까지의 첫 번째 v를 반환하고, 모든 플래그가 설정되어 있으면 n+1을 반환합니다.

첫 번째 예에서 n = 6입니다. 1, 2, 3, 5의 플래그가 설정되고, -2와 9는 건너뛰므로 설정되지 않은 첫 번째 플래그는 4입니다. 선형 순회를 두 번 수행하면 시간은 O(n)이고, 플래그에는 O(n)의 메모리가 필요합니다.

알고리즘

present를 생성하고, n+1개의 플래그를 false로 설정합니다.
nums의 각 값 v가 1 ≤ v ≤ n을 만족하면 present[v]를 true로 설정합니다.
플래그가 false인 1부터 n까지의 첫 번째 v를 반환합니다.
그런 값이 없으면 n+1을 반환합니다.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

각 값을 각각의 슬롯에 넣으세요

핵심 아이디어

값 v는 인덱스 v-1에 있어야 합니다. 1부터 n까지의 모든 값이 제자리에 있을 때, i+1을 갖고 있지 않은 첫 번째 인덱스 i가 답을 나타냅니다.

각 인덱스에서 값이 1과 n 사이에 있고 해당 값이 있어야 할 자리에 이미 그 값이 있지 않다면, 그 값을 제자리로 옮기도록 교환합니다. 되돌아온 값도 옮겨야 할 수 있습니다. i가 아니라 제자리를 확인하면 중복으로 인한 무한 반복을 막을 수 있습니다. [1, 1]에서는 두 번째 1이 인덱스 0에 1이 있는 것을 확인하고 그대로 남습니다.

첫 번째 예시에서는 인덱스 0이 5를 제자리로 보낸 다음, 되돌아온 2를 보냅니다. 이후 1과 3도 제자리로 가고 [1, 2, 3, -2, 5, 9]가 남습니다. 인덱스 3이 처음으로 잘못된 자리이므로 답은 4입니다.

각 교환은 값 하나를 영구적으로 제자리에 놓으므로, 내부 반복문에서 수행하는 교환은 총 n회 이하입니다. 따라서 시간 복잡도는 O(n)이고, R에서는 변경하는 벡터를 복사하므로 이를 제외하면 메모리 복잡도는 O(1)입니다.

알고리즘

0에서 n-1까지 각 인덱스 i에 대해:
1 ≤ nums[i] ≤ n이고 nums[nums[i]-1] ≠ nums[i]인 동안 nums[i]와 nums[nums[i]-1]을 바꿉니다.
배치 과정을 마친 후, nums[i] ≠ i+1인 첫 번째 인덱스 i를 찾아 i+1을 반환합니다.
모든 슬롯에 해당하는 값이 들어 있으면 n+1을 반환합니다.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

함정과 경계 사례

값이 있어야 할 자리에 값이 이미 있는지 확인하는 대신 nums[i] == i+1일 때 교환을 멈추는 경우입니다. [1, 1]에서는 두 개의 1이 계속 서로 교환됩니다.
while 대신 if를 사용해 교환하는 경우입니다. 첫 번째 예시에서는 인덱스 4에서 돌아온 2가 인덱스 1에 도달하지 못하고, 4 대신 2를 반환합니다.
nums[i] = nums[nums[i]-1]을 쓴 다음 다시 nums[i]로 인덱싱하는 경우입니다. 값이 바뀐 뒤의 값으로 해당 값이 있어야 할 인덱스를 읽게 됩니다. 인덱스를 먼저 저장하세요.
범위 검사를 건너뛰면 0, -2 또는 10^9가 배열 범위를 벗어난 인덱스로 전달됩니다.
모든 자리가 올바를 때 n을 반환하는 경우입니다. [4, 2, 1, 3]의 정답은 5입니다.

자주 묻는 질문3

First Missing Positive의 시간 복잡도는 얼마인가요?

배치 솔루션은 O(n) 시간과 O(1)의 추가 공간으로 실행됩니다. while 루프는 for 루프 안에 있지만, 각 교환은 값을 최종 인덱스에 놓으므로 전체 실행에서 교환은 최대 n번 이루어집니다. 플래그 배열 버전은 O(n) 시간과 O(n) 메모리를 사용하며, 각 후보를 스캔하면 O(n²)입니다.

답이 왜 n+1보다 큰 경우는 없나요?

1부터 n+1까지의 수는 서로 다른 n+1개의 값이고, 길이가 n인 배열에는 최대 n개의 서로 다른 값만 들어갈 수 있으므로 그중 하나가 누락됩니다. 배열에 1부터 n까지의 모든 값이 들어 있는 경우에만 정답은 n+1입니다.

제자리(in-place) 솔루션은 입력 배열을 변경하나요?

네, 값의 순서를 바꿉니다. 호출하는 쪽에서 원래 순서가 필요하다면 먼저 배열을 복사하세요. 그러면 추가 메모리 사용량이 다시 O(n)이 됩니다. 또 다른 제자리 방식은 1부터 n까지의 범위를 벗어나는 모든 값을 n+1로 바꾼 다음, nums[v-1]를 음수로 만들어 v가 존재함을 표시합니다. 이 방법도 배열을 변경합니다.

def firstMissingPositive(nums):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

nums = [5, -2, 1, 3, 2, 9]

예상 출력

First Missing Positive

함수

제약 조건

예제

힌트

풀이

각 후보를 전체 스캔으로 시도하세요

플래그 배열에서 1부터 n까지의 값을 표시합니다

각 값을 각각의 슬롯에 넣으세요

함정과 경계 사례

자주 묻는 질문3

비슷한 문제