[LeetCode]41. First Missing Positive

Problem

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

1
2
3
4
5
6
7
8
9
10
11
12
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.

Solution

Analysis

给定一个未排序的数组,查找没有出现过的最小的正整数.比如第一个例子,1,2都出现了,所以答案是3; 第二个例子是2. 所以,最简单的方法是将原数组变成一个set[因为数组中数字出现的次数和词序都无关紧要], 然后在范围1-size内对集合进行查找,如果没找到,直接返回; 如果找到,继续查找下一个,直到查找完毕,返回size+1. 但是这种方法空间复杂度是O(N), 不符合空间要求.

如果对数组排序,然后依次数组查找,不符合时间复杂度要求O(N). 如果采用基数排序呢? 符合时间要求和但是不符合空间复杂度要求常量空间–需要10个数组.

所以常见的方法都不适用.

这里使用数组本身作为1-size数字出现与否的记录数组: 调整数组顺序,使得1出现在下标0的位置,2出现在下标1的位置(实现方式是数字交互), 同时忽略0/负数/大于size的数. 处理完毕之后,我们再遍历数组,如果出现num[i] != i+1, 说明,这个数字没有出现在数组中,返回i+1. 如果遍历结束,还没有返回结果,返回size+1.

使用数组本身作为辅助数组,判断数字是否出现在数组中.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
// 数字做下标: 0: 1, 1: 2, etc. nums[i] == i+1
int size = nums.size();

for (int i=0; i< size; i++){
// 限制了范围
while (nums[i] > 0 && nums[i] <= size && nums[nums[i]-1] != nums[i])
swap(nums[i], nums[nums[i]-1]);// 反复交换,直到nums[i] == i+1.
}

for (int i=0; i< size; i++)
if (nums[i] != i+1)
return i+1;
return size+1;
}
};

References

https://www.cnblogs.com/grandyang/p/4395963.html

相似问题: 数组中重复的数字

Problem

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

Code

分析问题,发现,数字范围都在0~n-1之间,而且有n个数字; 如果没有重复数字的话,排序完,数组中元素和下标符合关系:nums[i] == i; 也就是说,数字可以作为数组中下标的位置,根据这个关系,我们调整数组中元素的位置,如果发现,这个位置已经有元素了,而且和当前这个数字相等,说明找到了重复数字,如果遍历完还没有返回结果,那就说明没有重复数字,return false.

使用和上面方法相似的方法: 使用数组本身作为辅助数组.

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
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
if (numbers == nullptr || length == 0) return false;

for (int i=0; i<length; i++){
while (numbers[i] != i){
if (numbers[i] == numbers[numbers[i]]){
*duplication = numbers[i];
return true;
}
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
};
您的支持就是我更新的最大动力!谢谢!