东莞品牌做网站,如何获取网站根目录,案例分析网站,在手机怎样使用wordpress缺失的第一个正数
给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1#xff1a;
输入#xff1a;nums [1,2,0]
输出#xff1a;3
解释#xff1a;范围 [1,…缺失的第一个正数
给你一个未排序的整数数组 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 10e5-2e31 nums[i] 2e31 - 1
可惜捏只能想到用hashmap做个o(n)额外空间的做...(开辟空间了但是速度快hhh
class Solution:def firstMissingPositive(self, nums: List[int]) - int: # Mehashmap {}for i in range(len(nums)):if nums[i] not in hashmap:hashmap[nums[i]] 1 for i in range(len(nums)1):if i1 not in hashmap:return i1
想不到O n 1 的做法看看大佬的做法吧原地数组将元素交换至元素-1下标的位置
随后从头往后寻找对应不起来的位置然后返回就好了
class Solution:def firstMissingPositive(self, nums: List[int]) - int: def swap(nums,a,b):tmp nums[a]nums[a] nums[b]nums[b] tmp# 原地数组nbfor i in range(len(nums)):while 1nums[i]len(nums) and nums[i]!nums[nums[i]-1]:swap(nums,nums[i]-1,i)for i in range(len(nums)):if nums[i]!i1:return i1return len(nums)1
