41. First Missing Positive
缺失的第一个正数
Given an unsorted integer array nums, return the smallest missing positive integer.
提供一个为排序的数组，返回最小的缺失的正数
You must implement an algorithm that runs in O(n) time and uses constant extra space.
O(n)的时间复杂度，并且不能使用多余的空间。
Example 1:
Input: nums = [1,2,0]
Output: 3
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1 #从1 开始寻找，直到找到不存在的数值？
Constraints:
1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1
思考
O(n)的时间复杂度，并且不能使用多余的空间。那么就意味着只能循环一遍，然后找出那个值。
- 最小正数，遇到负数就跳过。
- 创建一个最小的数字的变量，遇到正数，就判断是不是最小的，并存储。
- 问题在于是无序的，该如何判断是否存在连续的值。不如再设计一个数值，遇到最小的就往后寻找连续的但是缺失的值。然后记录下来。但是这样的话时间复杂度就不是O(n)了。
- 试一下从一开始寻找，找到不存在的数值即返回。
'''
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
for i in range(1, 2**31):
if i not in nums:
return i
很明显的超时了。
答案解析
哈希表
哈希表是一种key-value 的存储形式。它的特性，让它可以在O(1)的时间复杂度内，进行快速查找。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)#因为在全部连续的情况下，列表中最大的数值也只可能是n+1
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
#将所有的负数变成n+1
for i in range(n):
num = abs(nums[i])
if num <= n:
nums[num - 1] = -abs(nums[num - 1])
#原地置换，如果一个数小于等于n，则将该下标的数值变成负的。
for i in range(n):
if nums[i] > 0:
return i + 1
# 循环遍历，如果找到第一个正数的下标。返回 下标+1
return n + 1
这次的算法，相当于把数组看成了哈希表。下标是key，内容是value。
值得注意的是，这边的算法里面，设置n为输入的列表的长度。如果是连续的数组的话，最大的数值只可能是n。
最后只考虑小于n的数值。
将负数或零转换成大于n的数值。
将1 到 n的范围内的数值，把他们和下标对应。将这个下标对应的数值设置成负数，相当于打上标签，从而后面进行判断。
最后循环判断如果还有数值大于零的，说明这个下标的数值是缺少了的。
时间成本O(3n)->O(n)
空间成本O(1)
置换法
相当于原地进行排序，将数值放到原先的顺序，即数值n放在n-1的下标位置上。再次遍历的时候判断找出数值。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
同样用len(nums)来代表最大的数值，然后循环遍历n，将每次下标的数据，和下标上value代表的下标的数据进行判断是否需要交换。这里用了while循环来判断，即，对同一个下标的数据持续进行交换，直到不能交换为止。
最后循环交换好顺序的数组，判断是否满足要求。
总结
列表相关的数据，可以将下标看作key进行处理。
虽然我一开始也想到这么做了。但是真的这么做的时候退缩了。还是自己不行
