难度: Hard
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1运行时间: 32 ms
内存: 14.8 MB
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
for i in range(len(nums)):
while 0 < nums[i] <= len(nums) and nums[i] != nums[nums[i]-1]:
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
for i in range(len(nums)):
if nums[i] != i+1:
return i + 1
return len(nums) + 1
本题解采用原地哈希的思想。目标是将所有在1到n范围内的数放到它们应该在的位置上（即值为i的数放在下标为i-1的位置上）。这样，第一个不满足nums[i] == i + 1的下标i就是缺失的最小正数。首先遍历数组，对于每个元素nums[i]，如果它在1到n的范围内且不在正确的位置上，就将它与nums[nums[i] - 1]交换，直到无法交换为止。然后再次遍历数组，找到第一个不满足nums[i] == i + 1的下标i，返回i + 1作为缺失的最小正数。如果所有数都在正确的位置上，则返回n + 1。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
for i in range(len(nums)):
# 将nums[i]放到正确的位置上，直到无法交换或nums[i]不在1到n的范围内
while 0 < nums[i] <= len(nums) and nums[i] != nums[nums[i]-1]:
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
# 找到第一个不在正确位置的元素
for i in range(len(nums)):
if nums[i] != i+1:
return i + 1
# 如果所有元素都在正确的位置，则返回n + 1
return len(nums) + 1
这个条件确保了只有当nums[i]不在其正确位置时才进行交换。正确的位置是指值x应该位于索引x-1的位置上。如果没有这个条件，即nums[i]已经等于nums[nums[i]-1]，则表示nums[i]已经在正确的位置上，无需再交换。如果忽略这个条件，交换操作可能会导致不必要的重复交换或更糟糕的是，当存在重复元素时可能导致无限循环。例如，如果两个相同的有效元素在错误的位置，没有这个条件，它们会不断交换，永远不会停止。
在处理包含重复数字的数组时，上述算法仍然有效，因为算法主要关注将每个元素放在其正确的位置（即值i应该在位置i-1）。即使存在重复，重复的元素会尝试放入其应有的位置，但由于条件检查（nums[i] != nums[nums[i]-1]），不会导致错误的元素放置。然而，重复元素可能会导致一些不必要的交换操作，在某些情况下可能会略微降低效率，但不会影响算法的最终正确性。
如果数组中的每个数字都恰好处在其正确的位置上（即值i位于索引i-1），这意味着数组包含了从1到n的所有正整数。在这种情况下，数组中不存在间隙，缺失的最小正数就是紧接在这个连续序列之后的下一个整数，即n + 1。这种情况通常发生在数组正好是从1到n的一个排列的时候。
原地哈希方法依赖于数组中的每个位置能够存放一个正确的元素。该方法在处理非整数或非单一数据类型的数组时不适用，因为它需要数组元素和数组索引之间存在可预测的映射关系。如果数组过于稀疏（例如，大量的0或负数），虽然方法仍有效，但可能会导致效率低下，因为这些元素不会被放在任何有用的位置。另外，如果数组非常大或存在大量重复数据，虽然理论上仍然适用，但在实际操作中可能会遇到性能瓶颈。