Share my AC python code.


  • -1
    L

    The Key point is place the element in the right index position.
    However, it has a tap

    if you directly swap, [3,4,-1,1] will be swaped to [-1,1,3,4]. this is not right, it should be [1,-1,3,4].
    That's why reset the start to 0;
    Another way is recursive swap until the A[i] == A[A[i]-1];

    class Solution:
    # @param A, a list of integers
    # @return an integer
    def firstMissingPositive(self, A):
        i=0;
        while(i<len(A)):
            if(0<A[i]<=len(A)):
                if(A[i]!=A[A[i]-1]):
                    tmp=A[i];
                    A[i]=A[A[i]-1];
                    A[tmp-1]=tmp;
                    i=-1;  # key point, start from zero to scan again.
            i+=1;
    
        for i in range(len(A)):
            if(A[i]!=i+1):
                return i+1;
        return len(A)+1;

  • 0
    H

    it is basically java code. you don't need all the () in while and if.


Log in to reply
 

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