万网空间登录成品网站seo
这个算法的核心思想是通过交换操作，将每个数放到它应该在的位置上。然后再次遍历数组，找到第一个不在正确位置上的数，其索引加一即为缺失的最小正整数。
def first_missing_positive(nums):n = len(nums)# 第一次遍历，将数组中的每个数放到正确的位置上for i in range(n):while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]# 第二次遍历，找到第一个不在正确位置上的数，即为缺失的最小正整数for i in range(n):if nums[i] != i + 1:return i + 1# 如果数组中所有数都在正确位置上，则缺失的是数组长度+1return n + 1
这个算法的时间复杂度是 O(n)，因为每个数最多进行两次交换操作，而且只进行了两次遍历。额外空间复杂度是 O(1)，因为只使用了常数级别的额外空间。
原地哈希算法的原理是通过修改输入数据本身，将数据映射到正确的位置上，从而完成一些特定的操作。在具体的场景中，原地哈希算法通常用于解决一些空间复杂度受限制的问题，以达到在常数级别的额外空间内完成操作的目的。
for i in range(n):while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
-
在这一步中，如果 nums[i] 不在正确的位置上，并且它应该在的位置上的数不等于它，就进行交换。
-
第二次遍历：找到第一个不在正确位置上的数，即为缺失的最小正整数。
-
for i in range(n):
if nums[i] != i + 1:
return i + 1
在这一步中，如果 nums[i] 不等于 i + 1，说明 i + 1 是缺失的最小正整数。
这样，通过两次遍历和原地交换的方式，就可以在常数级别的额外空间内找到未排序整数数组中缺失的最小正整数。
原地哈希算法通常涉及到将数据按某种规则重新排列，以满足问题的要求，而不需要额外的数据结构来存储中间结果。