[LeetCode] 41. First Missing Positive

轉自LeetCode

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

<Solution>

這題比較麻煩的部分是，題目要求時間複雜度 O(n) 且空間複雜度要 O(1)

解題想法如下

• 每個 index 放相對應的數值，例如 index 0 放的是 1，index 1 放的是 2。關係是 A[i] = A[A[i] - 1]

• 如果A[i] > 0 且 A[i] <= nums.size()，就檢查 A[i] == A[A[i] - 1]，不是的話就對調

• 找第一個不符合規則到 index，回傳 index + 1

• 如果找不到，那就代表沒有缺失 positive integer，且是升冪排列，所以回傳 nums.size() + 1

code 如下

c++

Kotlin