牛客. 数组中未出现的最小正整数
1 题目
给定一个无序数组arr，找到数组中未出现的最小正整数
例如arr = [-1, 2, 3, 4]。返回1
arr = [1, 2, 3, 4]。返回5
[要求]
时间复杂度为O(n)，空间复杂度为O(1)
链接：https://www.nowcoder.com/questionTerminal/030cabe03d94484c819e87c2e38c41bd?f=discussion
来源：牛客网
输入描述:
第一行为一个整数N。表示数组长度。
接下来一行N个整数表示数组内的数
输出描述:
输出一个整数表示答案
示例1
输入
4
-1 2 3 4
输出
1
示例2
输入
4
1 2 3 4
输出
5
2 解析
合法的元素序列是，索引和nums元素对应，即索引0对应1，索引1对应2，依次递增。
边排序，边判断不合法元素的位置。
不合法的情况有三种：
- 当前值小于索引
- 当前值大于索引
- 当前值与前面的元素重复
3 Python实现
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
i = 0
while (i<n):
# 合法的情况：nums中元素与索引对应。索引0对应1，索引1对应2，依次递增
if nums[i]==i+1:
i+=1
'''
出现不合法情况
1.nums的当前值小于索引
2.nums的当前值大于索引
3.nums当前值出现了重复
'''
elif (nums[i]<=i or nums[i]>n or nums[nums[i]-1]==nums[i]):
n -=1
nums[i] = nums[n]
# 表示当前值是一个合法的值，但是没有在理想的位置上，需要进行交换处理
else:
temp = nums[i]
nums[i] = nums[nums[i]-1]
nums[temp-1] = temp
return i+1
