topic41

41.缺失的第一个正数

1. 题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 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 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

标签 数组 哈希表

2. 解题

如果不限制空间, 使用哈希表记录出现过的所有正数及其中的最大值。然后从1遍历到最大值，返回其中第一个哈希表中不存在的数

采用置换的思想，依次将数组中的数字置换到对应下标-1出，最后再次遍历，若位置不匹配，则返回此时的下标+1