Sharing my 8ms c++ accepted solution


  • 1
    R
    class Solution {
    public:
    int firstMissingPositive(int arr[], int n) {
        
        int i, temp;
        
        for (i = 0; i < n; i++)
        {
            while(arr[i] != i+1 && arr[i] > 0 && arr[i] <= n && arr[i] != arr[arr[i]-1])
            {
                temp = arr[arr[i]-1];
                arr[arr[i]-1] = arr[i];
                arr[i] = temp;
            }
        }
        
        for(i = 0; i < n; i++)
        {
            if (arr[i] != i+1)
                return i+1;
        }
        
        return i+1;
    }
    };

  • 0
    X

    Nice implementation! My Python version based on your idea. Thanks for sharing!

    class Solution:
        # @param A, a list of integers
        # @return an integer
        def firstMissingPositive(self, A):
            #works when A contains duplicates
            for i in range(len(A)):
                num = A[i]
                while num <= len(A) and num > 0:
                    if num != A[num-1]:
                        temp = A[num-1]
                        A[num-1] = num
                        num = temp
                    else:
                        break
            for i in range(len(A)):
                if A[i] != i+1:
                    return i+1
            return len(A)+1

  • 0
    K
    This post is deleted!

  • 0
    Z

    I think the condition of "arr[i] != i-1" can be not neccessary!!


Log in to reply
 

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