Hard
max+1
尝试写一下代码,AC!
python3
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
if len(nums) is 0:
return 1
m = max(nums)
if m <= 0:
return 1
for i in range(1,m+1):
if i not in nums:
return i
return m + 1
使用哈希表能减少in
操作的时间复杂度。
但是这道题的难度定的是Hard。主要难点在于限制条件:时间复杂度为O(n),使用空间复杂度为O(1)
如果使用Hash表,时间复杂度可以用到\(O(n)\),但是需要用到\(O(n)\)的空间复杂度;如果不使用Hash表,直接遍历原数组进行判断的话,时间复杂度为\(O(n^2)\)
所以,如果这道题想到完全符合题目要求的话,还需要寻找别的方法
新思路
阅读大佬们的解题获得新思路,新思路还是哈希表。但是这边不是使用默认的set,而是我们自己构造一张哈希表
这个思路主要参考李威威大佬解题中的方法三:点我前往
1
这个数放到下标为0
的位置,2
这个数放到下标为1
的位置,然后再遍历一次数组,第1
个遇到的它的值不等于下标的那个数,就是我们要找的缺失的第一个正数。数值为 i 的数映射到下标为 i - 1 的位置
python3
class Solution:
# 3 应该放在索引为 2 的地方
# 4 应该放在索引为 3 的地方
def firstMissingPositive(self, nums: List[int]) -> int:
size = len(nums)
for i in range(size):
# 先判断这个数字是不是索引,然后判断这个数字是不是放在了正确的地方
while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
self.__swap(nums, i, nums[i] - 1)
for i in range(size):
if i + 1 != nums[i]:
return i + 1
return size + 1
def __swap(self, nums, index1, index2):
nums[index1], nums[index2] = nums[index2], nums[index1]