当前位置 博文首页 > lh_lyh的博客：LeetCode 41. 缺失的第一个正数
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
相似题目：LeetCode 448. 找到所有数组中消失的数字、LeetCode 442. 数组中重复的数据
此题依旧可以沿用上述相似题目的思路，用索引作为哈希表
将不用考虑的数：不在1-n范围内的数字用1代替，这样方便统一操作。
在用1替换掉非法数字之前，先判断数组中有无1存在，没有的话直接返回1，有的话就可以用1替换。
现在所有数字都在1-n范围内，遍历每个元素，将元素值对应的索引位置上的元素置为非法状态（可以选择取负、+n等操作，下面代码选择取负操作）。
遍历数组，遇到的第一个合法状态元素的对应的索引就是缺失的最小正数，因为原始数组元素没有它，就没有对其进行非法操作。
tip：为方便1-n数字与索引一一对应，
1~n-1对应索引1~n-1，n对应索引0。
具体代码如下：
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
# 基本情况
if 1 not in nums:
return 1
# nums = [1]
if n == 1:
return 2
# 用 1 替换负数，0，
# 和大于 n 的数
# 在转换以后，nums 只会包含
# 正数
for i in range(n):
if nums[i] <= 0 or nums[i] > n:
nums[i] = 1
# 使用索引和数字符号作为检查器
# 例如，如果 nums[1] 是负数表示在数组中出现了数字 `1`
# 如果 nums[2] 是正数 表示数字 2 没有出现
for i in range(n):
a = abs(nums[i]) # 这里加abs是防止前面重复出现过，已经更改为负数了。
# 如果发现了一个数字 a - 改变第 a 个元素的符号
# 注意重复元素只需操作一次
if a == n:
nums[0] = - abs(nums[0])
else:
nums[a] = - abs(nums[a])
# 现在第一个正数的下标
# 就是第一个缺失的数
for i in range(1, n):
if nums[i] > 0:
return i
if nums[0] > 0:
return n
return n + 1
交换到应该在的位置上，比较元素和索引值。
交换位置时遇到非正数或者 >n 的数停止。
具体代码如下：
void swap(vector<int>&nums, int i, int j) {
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
int firstMissingPositive(vector<int>& nums) {
int len = nums.size();
int res = 0;
for (int i = 0; i < len; i++) {
if(nums[i] <= 0 || nums[i] > len) // 非法数字不进行操作
continue;
while (nums[i] != i + 1) { // 不在正确位置上
if(nums[i] <= 0 || nums[i] > len) // 交换遇到非法数字时停止
break;
else if (nums[i] != nums[nums[i] - 1]) { // 正确位置：nums[i] - 1，不相等时进行交换
swap(nums,i,nums[i] - 1);
}
else
break;
}
}
bool s = false; // 判断数字是否在n范围内
for (int i = 0; i < len; i++) {
if (nums[i] != i+1){
res = i+1;
s = true;
break;
}
}
res = s == true ? res : len+1;
return res;
}
