这个有问题，死循环，目前还么有找到错误
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 1
n = len(nums)
i = 0
while i < n:
if nums[i] != i+1 and nums[i] >= 1 and nums[i] <= n and nums[nums[i] - 1] != nums[i]:
temp = nums[i]
nums[i] = nums[nums[i] - 1]
nums[nums[i] - 1] = temp
else:
i += 1
for j in range(n):
if nums[j] != j+1:
break
return j+1
思想都是差不多，不管负数和超过长度的整数，把在1到n的数字留在相应的位置：保证nums[i-1]==nums[i]
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 1
n = len(nums)
for i in range(n):
# if nums[i] > n:
# continue
val = nums[i] - 1
while nums[i] > 0 and nums[i] <= n and nums[val] != nums[i]:
nums[i],nums[val] = nums[val],nums[i]
val = nums[i] - 1
for i in range(n):
if nums[i] != i+1:
return i + 1
return n+1
···
另外一种方法：
class Solution:
# @param A, a list of integers
# @return an integer
# @a very subtle solution
def firstMissingPositive(self, A):
n=len(A)
for i in range(n):
if A[i]<=0: A[i]=n+2
for i in range(n):
if abs(A[i])<=n:
curr=abs(A[i])-1
A[curr]=-abs(A[curr])
for i in range(n):
if A[i]>0: return i+1
return n+1
