0%

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i)
while(0 < nums[i] && nums[i] <= nums.size() && nums[i] != nums[nums[i] - 1])
swap(nums[i], nums[nums[i] - 1]);

for (int i = 0; i < nums.size(); ++i)
if (nums[i] != (i + 1))
return i + 1;
return nums.size() + 1;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)):
while 0 < nums[i] <= len(nums) and nums[i] != nums[nums[i] - 1]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]

for i in range(len(nums)):
if i + 1 != nums[i]:
return i + 1
return len(nums) + 1

ps:

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

最好是用上面的临时变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
# @param A, a list of integers
# @return an integer
def firstMissingPositive(self, A):
i, n =0,len(A)
while i < n:
if A[i] > 0 and A[i] <= n and A[A[i] - 1] != A[i] :
A[A[i] - 1] , A[i] = A[i], A[A[i] - 1]
#A[i], A[A[i] - 1] = A[A[i] - 1] , A[i] error!
else:
i+=1

for i in range(n):
if A[i] != i + 1 :
return i + 1
return n + 1

 

本文是leetcode如下的题解

  • 41. First Missing Positive

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

请我喝杯咖啡吧~