Accepted solution in python


  • 0
    L
            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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.