class Solution: # @param A, a list of integers # @return an integer def firstMissingPositive(self, A): head,tail=0,len(A)-1 # reorder A to ensure the first head elements are positive number while head<=tail: if A[head]<=0 and A[tail]>0: A[head],A[tail]=A[tail],A[head] head,tail=head+1,tail-1 elif A[head]>0: head+=1 elif A[tail]<=0: tail-=1 # check each element and if the value is smaller than head, reverse the sign of the corresponding number at that index. #The one that have not been reversed are element that are missing. #And the first index would be the smallest integer that is missing. for i in range(head): if abs(A[i])<=head: A[abs(A[i])-1]=-abs(A[abs(A[i])-1]) for i in range(head): if A[i]>0: return i+1 return head+1
Accepted solution in python
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.