效果图网站大全,网页传奇游戏排行榜前十,科技公司取名大全,无锡专业制作外贸网站的公司这个算法的核心思想是通过交换操作#xff0c;将每个数放到它应该在的位置上。然后再次遍历数组#xff0c;找到第一个不在正确位置上的数#xff0c;其索引加一即为缺失的最小正整数。
def first_missing_positive(nums):n len(nums)# 第一次遍历#xff0c;将数组中的每…
这个算法的核心思想是通过交换操作将每个数放到它应该在的位置上。然后再次遍历数组找到第一个不在正确位置上的数其索引加一即为缺失的最小正整数。
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 是缺失的最小正整数。
这样通过两次遍历和原地交换的方式就可以在常数级别的额外空间内找到未排序整数数组中缺失的最小正整数。
原地哈希算法通常涉及到将数据按某种规则重新排列以满足问题的要求而不需要额外的数据结构来存储中间结果。
