Leetcode练习(Python)：数组类：第41题：给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
标签：tail 创建 数组类 练习 hashmap 空间 测试用例 十分 无法
题目：给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
思路：第一个思路是创建一个锚点，这个锚点表示第一个正整数的出现的位置，然后再分情况来判断，结果程序无法通过所有的测试用例，第一个思路方法以后再实现，后来使用HashMap来说实现，十分方便。
程序1：HashMap
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
length = len(nums)
hashmap = [0] * length
for x in nums:
if x > 0 and x
hashmap[x - 1] = x
for index in range(length):
if hashmap[index] != index + 1:
return index + 1
return length + 1
程序2：类似专家系统（此程序有问题，待修正）
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
nums.sort()
length = len(nums)
if length
return 1
if length == 1:
if nums[0]
return 1
elif nums[0] == 1:
return 2
else:
return 1
#Find the first positive integer as anchor
for index in range(length):
if nums[index] > 0:
anchor = index
break
else:
anchor = length - 1
#temp_index is the first anchor
#anchor in the head
if anchor == 0:
if nums[anchor] == 1:
while anchor
#anchor += 1
if nums[anchor] - nums[anchor - 1] > 1:
return nums[anchor - 1] + 1
break
elif nums[anchor] - nums[anchor - 1] == 1 and anchor - 1
anchor += 1
elif nums[anchor] - nums[anchor - 1] == 0 and anchor - 1
anchor += 1
if anchor >= length - 1:
anchor = length - 1
return nums[anchor] + 1
break
else:
return 1
#anchor in the tail
elif anchor == length - 1:
if nums[anchor]
return 1
elif nums[anchor] > 1:
return 1
else:
return nums[anchor] + 1
#anchor in the body
else:
while anchor
anchor += 1
if nums[anchor] - nums[anchor - 1] > 1:
return nums[anchor - 1] + 1
break
elif nums[anchor] - nums[anchor - 1] == 1 and anchor + 2
anchor += 1
elif nums[anchor] - nums[anchor - 1] == 0 and anchor + 2
anchor += 1
if anchor >= length - 1:
anchor = length - 1
return nums[anchor] + 1
break
#anchor += 1
#return anchor
Leetcode练习(Python)：数组类：第41题：给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
标签：tail 创建 数组类 练习 hashmap 空间 测试用例 十分 无法
原文地址：https://www.cnblogs.com/zhuozige/p/12732315.html
评论