Description#
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
Example 1:
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.
Constraints:
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
Solutions#
Solution 1: In-place Swap#
We assume the length of the array $nums$ is $n$, then the smallest positive integer must be in the range $[1, .., n + 1]$. We can traverse the array and swap each number $x$ to its correct position, that is, the position $x - 1$. If $x$ is not in the range $[1, n + 1]$, then we can ignore it.
After the traversal, we traverse the array again. If $i+1$ is not equal to $nums[i]$, then $i+1$ is the smallest positive integer we are looking for.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
def swap(i, j):
nums[i], nums[j] = nums[j], nums[i]
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
swap(i, nums[i] - 1)
for i in range(n):
if i + 1 != nums[i]:
return i + 1
return n + 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < n; ++i) {
if (i + 1 != nums[i]) {
return i + 1;
}
}
return n + 1;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (i + 1 != nums[i]) {
return i + 1;
}
}
return n + 1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func firstMissingPositive(nums []int) int {
n := len(nums)
for i := range nums {
for nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i]-1] {
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
}
}
for i, v := range nums {
if i+1 != v {
return i + 1
}
}
return n + 1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function firstMissingPositive(nums: number[]): number {
const n = nums.length;
let i = 0;
while (i < n) {
const j = nums[i] - 1;
if (j === i || j < 0 || j >= n || nums[i] === nums[j]) {
i++;
} else {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
const res = nums.findIndex((v, i) => v !== i + 1);
return (res === -1 ? n : res) + 1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| impl Solution {
pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut i = 0;
while i < n {
let j = nums[i] - 1;
if (i as i32) == j || j < 0 || j >= (n as i32) || nums[i] == nums[j as usize] {
i += 1;
} else {
nums.swap(i, j as usize);
}
}
(
nums
.iter()
.enumerate()
.position(|(i, &v)| (v as usize) != i + 1)
.unwrap_or(n) as i32
) + 1
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| public class Solution {
public int FirstMissingPositive(int[] nums) {
var i = 0;
while (i < nums.Length)
{
if (nums[i] > 0 && nums[i] <= nums.Length)
{
var index = nums[i] -1;
if (index != i && nums[index] != nums[i])
{
var temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
else
{
++i;
}
}
else
{
++i;
}
}
for (i = 0; i < nums.Length; ++i)
{
if (nums[i] != i + 1)
{
return i + 1;
}
}
return nums.Length + 1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int firstMissingPositive(int* nums, int numsSize) {
int Max = nums[0], i, *Count;
for (i = 1; i < numsSize; i++) {
Max = (Max < nums[i]) ? nums[i] : Max;
}
Count = (int*) calloc(Max + 1, sizeof(int));
for (i = 0; i < numsSize; i++) {
if (nums[i] > 0) {
Count[nums[i]]++;
}
}
i = 1;
while (Count[i] != 0) {
i++;
}
return i;
}
|
Solution 2#
1
2
3
4
5
6
7
8
| function firstMissingPositive(nums: number[]): number {
const set = new Set(nums);
let ans = 1;
while (true) {
if (!set.has(ans)) return ans;
ans++;
}
}
|
