即墨网站建设公司企业网站怎么做的

即墨网站建设公司,企业网站怎么做的,广东短视频seo营销,wordpress建站教程网给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1#xff1a; 输入#xff1a;nums [1,2,0] 输出#xff1a;3 解释#xff1a;范围 [1,2] 中的数字都在数组…给你一个未排序的整数数组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 -231 nums[i] 解题思路要在 O (n) 时间复杂度和常数级额外空间内解决问题核心思路是原地哈希标记范围确定缺失的最小正整数一定在[1, n1]范围内n 为数组长度。例如数组长度为 3若 1、2、3 都存在则返回 4否则返回缺失的最小数。过滤无效值将数组中所有≤0 或 n 的数替换为n1这些数不可能是目标替换后不干扰后续标记。标记存在的数遍历数组对每个元素x取绝对值若x ≤ n则将数组第x-1位标记为负数表示x这个数存在。查找缺失值遍历数组第一个正数的位置i1就是缺失的最小正整数若全为负数说明 1~n 都存在返回n1。示例验证示例 1输入nums [1,2,0]过滤无效值0 替换为 4 →[1,2,4]标记存在的数x1 → nums[0] -1x2 → nums[1] -2x43→ 不处理数组变为[-1,-2,4]遍历找正数索引 2 是第一个正数返回213符合预期。示例 2输入nums [3,4,-1,1]过滤无效值-1 替换为 54 替换为 5 →[3,5,5,1]标记存在的数x3 → nums[2] -5x54→ 不处理x54→ 不处理x1 → nums [0] -3数组变为[-3,5,-5,1]遍历找正数索引 1 是第一个正数返回112符合预期。示例 3输入nums [7,8,9,11,12]过滤无效值所有数 5替换为 6 →[6,6,6,6,6]标记存在的数所有 x65→ 不处理数组仍为[6,6,6,6,6]遍历找正数索引 0 是第一个正数返回011符合预期。核心优势时间复杂度 O (n)仅三次线性遍历无嵌套操作空间复杂度 O (1)仅使用常数级临时变量原地修改数组鲁棒性处理了负数、重复值、超大数等边界场景适配题目 10⁵级别的数组长度。Python代码from typing import List class Solution: def firstMissingPositive(self, nums: List[int]) - int: n len(nums) # 过滤无效值 for i in range(n): if nums[i] 0 or nums[i] n: nums[i] n 1 # 标记存在的数 for i in range(n): x abs(nums[i]) if x n: nums[x - 1] -abs(nums[x - 1]) # 查找缺失值 for i in range(n): if nums[i] 0: return i 1 return n 1 # 测试用例 if __name__ __main__: solution Solution() # 示例1 nums1 [1,2,0] print(f示例1输入: {nums1}) print(f示例1输出: {solution.firstMissingPositive(nums1)}) # 示例2 nums2 [3,4,-1,1] print(f示例2输入: {nums2}) print(f示例2输出: {solution.firstMissingPositive(nums2)}) # 示例3 nums3 [7,8,9,11,12] print(f示例3输入: {nums3}) print(f示例3输出: {solution.firstMissingPositive(nums3)}) # 边界用例1~n都存在 nums4 [1,2,3,4] print(f示例4输入: {nums4}) print(f示例4输出: {solution.firstMissingPositive(nums4)}) # 边界用例空值/重复值 nums5 [2,2,2] print(f示例5输入: {nums5}) print(f示例5输出: {solution.firstMissingPositive(nums5)})LeetCode提交代码from typing import List class Solution: def firstMissingPositive(self, nums: List[int]) - int: n len(nums) # 步骤1过滤无效值≤0 或 n的数替换为n1不干扰后续标记 for i in range(n): if nums[i] 0 or nums[i] n: nums[i] n 1 # 步骤2标记存在的正整数用负数标记表示对应数存在 for i in range(n): x abs(nums[i]) # 取绝对值避免已标记的负数干扰 if x n: # 仅处理1~n范围内的数 nums[x - 1] -abs(nums[x - 1]) # 标记为负数重复标记不影响 # 步骤3查找第一个未标记的位置正数返回i1 for i in range(n): if nums[i] 0: return i 1 # 所有1~n都存在返回n1 return n 1程序运行结果如下示例1输入: [1, 2, 0] 示例1输出: 3 示例2输入: [3, 4, -1, 1] 示例2输出: 2 示例3输入: [7, 8, 9, 11, 12] 示例3输出: 1 示例4输入: [1, 2, 3, 4] 示例4输出: 5 示例5输入: [2, 2, 2] 示例5输出: 1总结本文提出了一种在O(n)时间复杂度和常数空间内寻找数组中缺失最小正整数的算法。核心思路是通过原地哈希标记首先过滤无效值≤0或n的数然后利用数组索引标记存在的正整数1~n最后扫描数组找到第一个未被标记的位置。该方法高效处理了各种边界情况负数、重复值、超大数等并通过三个线性遍历实现最优复杂度。Python实现验证了算法的正确性适用于LeetCode等编程挑战。