【每日一题】41. First Missing Positive
【每日一题】41. First Missing Positive
问题描述
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3Example 2:
Input: [3,4,-1,1]
Output: 2Example 3:
Input: [7,8,9,11,12]
Output: 1Follow up:
Your algorithm should run in O(n) time and uses constant extra space.
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
题解
马上想出满足条件复杂度为O(n)，空间复杂度为O(1)的方法比较困难。先不过题目中的限制条件，看看这道题应该怎么解，然后再想着如何对这个方法进行改进使得满足题目要求。
第一个想法是，如果对数组进行排序，然后从排序后第一个正数所在的位置开始，依次比较是否等于【1，N】，返回第一个缺失的正数。
另一个想法是，我们先圈定一组正数:[1, size]，对其中的每个正数，判断是否在给定的数组中，如果不在，则返回对应的正数；如果都在返回size+1.
对应代码：
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
if (nums.empty()) return 1;
int size = nums.size();
for(int i=1; i<=size; i++){
int j = 0;
for (; j< size; j++){
if (i == nums[j])
break;
}
if (j >= size)
return i;
}
return size+1;
}
};但是这种方法的时间复杂度为O(N**2)，空间复杂度为O(N)不符合题目要求。但是可以提交！
毕竟不满足题目要求，再想想如何修改。
利用有序这个点，因为返回的是最小的缺失正数，之前的解法先确定了一个升序排序的正数序列，如果第一次发生缺失，返回这个数即可。这里的话，我们利用这个想法，将给定数组进行调整，使得元素按照从小到大的顺序放到确定的位置上，这个顺序从下表0开始，对应的数字应该是第一个整数即1；数字放置的条件是 nums[i] > 0 and nums[i] <= size and nums[nums[i]-1] != nums[i];依次遍历所有元素；最后遍历整个数组,返回第一个nums[i] != i+1的数字。
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]);
}
for (int i=0; i< size; i++)
if (nums[i] != i+1)
return i+1;
return size+1;
}
};