外贸网站建设流程,外贸客户如何开发,免费模板网站都有什么区别,济南建设高端网站代码 测试用例
测试用例
测试结果
41. 缺失的第一个正数
已解答
困难
相关标签
相关企业
提示
给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1#xf…代码 测试用例
测试用例
测试结果
41. 缺失的第一个正数
已解答
困难
相关标签
相关企业
提示
给你一个未排序的整数数组 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 105-231 nums[i] 231 - 1
class Solution(object):def firstMissingPositive(self, nums)::type nums: List[int]:rtype: int# 得到最大值正数最小值# 不能排序因为排序nlogn# 只能利用原本的数字存储了for i ,val in enumerate(nums):while nums[i]0 and nums[i]len(nums) and nums[i]!i1 and nums[nums[i]-1] ! nums[i]:temp nums[i]nums[i] nums[temp-1]nums[temp-1] tempfor i in range(len(nums)):if nums[i]!i1:return i1return len(nums)1
首先题目的要求是空间为常熟 所以不能使用hash表
那么我们只能用原本的数组去处理了
所以我们的方法是把符合条件的正整数也就是1-》len(nums)的数放到他的值减一的下标处这样遍历一遍就知道少了哪个了。
需要考虑多种情况
1. 当你把一个数换过去之后换回来的数还需要继续换所以我们的for里面用while处理
2. 当你把数换过来之后可能那个地方本来就已经有一个数占据位置了也就是[1,1]的情况这样会导致死循环所以你需要把这种情况当做看不见。因为放到原处也是一个不合理值反正要放到的地方已经有合理值了。
