leetcode First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.


题目地址:leetcode First Missing Positive

题目大意: 给定一些数,找出第一个没有出现的正数。 要求时间复杂度O(n) 空间复杂度O(1)

思路:

将值为i的数放在下标i-1的位置,即:nums[i]存放的应该是i+1这个数。

因此,若以下条件均满足

  1. i  + 1 != nums[i]
  2. 0 < nums[i] <= len(nums)
  3. nums[i] != nums[nums[i] – 1]

则可以交换。

第一个条件说明当前位置不满足条件。

第三个条件说明nums[i]应该放在nums[nums[i] – 1]这个位置上,若那个位置不是nums[i]则交换

第二个条件保证第三个条件的下标不会越界。

 

在交换完之后,扫描数组,若nums[i] != i + 1则返回i+ 1,若都满足说明缺的是len(nums) + 1

为什么是对的?

因为我们把 值为x的放入了x-1的位置,那么1放入0的位置,len(nums) 放入len(nums) -1的位置。

如果存在值为x的数,那么上面的交换过程保证了位置x-1放置了x。

下面的代码中,第一个条件和第三个合并了,只需要第三个条件即可。(推导一下很显然的,若i + 1 == nums[i],则 nums[i] == nums[i + 1 – 1])

C++

Python

ps:

以前被py的交换坑了一把,写成如下的第九行就进入死循环。

最好是用上面的临时变量

 

本文是leetcode如下的题解

  • 41. First Missing Positive

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode First Missing Positive
本文地址:https://www.hrwhisper.me/leetcode-first-missing-positive/

您的支持将鼓励我继续创作!

Leetcode . permalink.

4 thoughts on “leetcode First Missing Positive

Leave a Reply

Your email address will not be published. Required fields are marked *