【Leetcode刷题Python】牛客. 数组中未出现的最小正整数

牛客. 数组中未出现的最小正整数 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