目录
1、题目
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O ( n ) O(n) O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
提示：
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1
2、思路
(桶排序） O ( n ) O(n) O(n)
对于一个长度为 n 的数组，其中没有出现的最小正整数只能在[1,n+1]中。这是因为如果[1,n] 都出现了，那么答案是 n+1，否则答案是[1,n]中没有出现的最小正整数。
我们使用桶排序的思想：
-
1、数组长度是
n，我们通过某种规律的交换恢复数组，使得,nums[0] = 1,nums[1] = 2…nums[n - 1] = n，即恢复完的数组中的每个数都应满足nums[i] = i + 1，如果某个nums[i]不满足，说明数组中缺失该i+1数。以[3, 4, -1, 1]为例：恢复后的数组应当为[1, -1, 3, 4]，其中nums[1] ! = 2 (1 + 1)我们就可以知道缺失的数为2。 -
2、那么我们如何将数组进行恢复呢？我们发现数组的值
num[i]和下标i有一定的关系，即nums[i] == nums[nums[i]-1]，下标i == nums[i] - 1。 -
3、因此我们可以对数组进行一次遍历。对于处在
[1,n]之间的数nums[i],如果其nums[i] ！= nums[nums[i]-1]，我们就将nums[i],nums[nums[i] - 1]不断进行交换，直到nums[i] ！= nums[nums[i]-1]。 -
4、若存在不在
[1,n]区间的数时，则表示该数一定会在原数组占空间，且占到不能被对应的位置上，因此从小到大枚举，若nums[i] != i + 1，则表示i + 1这个数是第一个缺失的正数，若都没有缺失，那么n + 1就是第一个缺失的正数。
时间复杂度分析：
O
(
n
)
O(n)
O(n)，n是数组的长度。
空间复杂度分析： O ( 1 ) O(1) O(1) 。
3、c++代码
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( nums[i] != i + 1)
return i + 1;
}
return n + 1;
}
};
3、java代码
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])
{
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for(int i = 0; i < n ; i++)
{
if( nums[i] != i + 1)
return i + 1;
}
return n + 1;
}
}
原题链接： 41. 缺失的第一个正数