【力扣-41. 缺失的第一个正数 ✨】Python笔记

原地哈希的原理原地哈希的核心思想是利用数组本身的索引空间存储信息避免额外空间开销。对于正整数数组将数字x映射到索引x-1的位置。通过交换操作将数字归位到正确索引从而在遍历时快速判断缺失值。解题步骤数据预处理遍历数组将每个有效正整数1 ≤ x ≤ n交换到其对应的索引位置x-1。忽略无效数字负数、零或大于数组长度的数。交换逻辑使用while循环确保数字被正确归位。例如数字3应放置在索引2处。若目标位置已有正确值则跳过否则持续交换直到当前数字无法归位。查找缺失值再次遍历数组检查每个位置i的值是否为i1。若发现不匹配立即返回i1作为缺失的最小正整数。若全部匹配则返回n1。代码实现from typing import List class Solution: def firstMissingPositive(self, nums: List[int]) - int: n len(nums) for i in range(n): while 1 nums[i] n and nums[nums[i] - 1] ! nums[i]: correct_pos nums[i] - 1 nums[i], nums[correct_pos] nums[correct_pos], nums[i] for i in range(n): if nums[i] ! i 1: return i 1 return n 1复杂度分析时间复杂度每个元素最多被交换一次整体为 $O(N)$。空间复杂度仅使用常量额外空间为 $O(1)$。关键注意事项死循环预防交换前需检查目标位置是否已含正确值避免重复交换导致死循环。边界处理确保数组索引在有效范围内防止越界错误。极端情况如输入数组已包含1至n的所有数字应返回n1。