First Missing Positive

 First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Follow up:

Your algorithm should run in O(n) time and uses constant extra space.

C++

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

        if(nums.size()==0)return 1;

        if(nums.size()==1)

            if(nums[0]>1||nums[0]<1)

               return 1;

            else if(nums[0]==1)

                return 2;

        

         unordered_map<int,int> mp;

        for(int i=0;i<nums.size();++i)

        {

            if(nums[i]>0)

            {

                mp[nums[i]]++;

            }

        }

        long long int n=*max_element(nums.begin(),nums.end());

        if(n<1)return 1;

        int i=1;

        while(i<=n)

        {   

            if(mp[i]==0)

                return i;

            ++i;

        }

        return n+1;

        

    }

};

--------------------------------------------------------------------------------------------------------------------------------------

Put each number in the right place.

For example:

When we find 5, then swap it with A[4].

At last, the first place where its number is not right, 

return the place + 1.

class Solution

{

public:

    int firstMissingPositive(int A[], int n)

    {

        for(int i = 0; i < n; ++ i)

            while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])

                swap(A[i], A[A[i] - 1]);    

        for(int i = 0; i < n; ++ i)

            if(A[i] != i + 1)

                return i + 1;

        return n + 1;

    }

};

---------------------------------------------------------------------------------------------------------------------------------------

 PYTHON

def firstMissingPositive(self, nums):

    """

    :type nums: List[int]

    :rtype: int

     Basic idea:

    1. for any array whose length is l, the first missing 

    positive must be in range [1,...,l+1], 

        so we only have to care about those elements in this 

        range and remove the rest.

    2. we can use the array index as the hash to restore the 

    frequency of each number within 

         the range [1,...,l+1] 

    """

    nums.append(0)

    n = len(nums)

    for i in range(len(nums)): #delete those useless elements

        if nums[i]<0 or nums[i]>=n:

            nums[i]=0

    for i in range(len(nums)): #use the index as the hash to 

    record the frequency of each number

        nums[nums[i]%n]+=n

    for i in range(1,len(nums)):

        if nums[i]/n==0:

            return i

    return n

---------------------------------------------------------------------------------------------------------------------------------------------

JAVA

This code takes advantage of two insights:Numbers greater then n can be ignored because the missing integer must be in the range 1..n+1

If each cell in the array were to contain positive integers only, 

we can use the negative of the stored number as a flag to mark something (in this case the flag indicates this index was found in some cell of the array)

public class Solution {

public int firstMissingPositive(int[] nums) {

    int n = nums.length;

    

    // 1. mark numbers (num < 0) and (num > n) with a special

     marker number (n+1) 

    // (we can ignore those because if all number are > n then 

    we'll simply return 1)

    for (int i = 0; i < n; i++) {

        if (nums[i] <= 0 || nums[i] > n) {

            nums[i] = n + 1;

        }

    }

    // note: all number in the array are now positive, and on 

    the range 1..n+1    

    // 2. mark each cell appearing in the array, by converting 

    the index for that number to negative

    for (int i = 0; i < n; i++) {

        int num = Math.abs(nums[i]);

        if (num > n) {

            continue;

        }

        num--; // -1 for zero index based array 

        (so the number 1 will be at pos 0)

        if (nums[num] > 0) { 

        // prevents double negative operations

            nums[num] = -1 * nums[num];

        }

    }

    // 3. find the first cell which isn't negative

     (doesn't appear in the array)

    for (int i = 0; i < n; i++) {

        if (nums[i] >= 0) {

            return i + 1;

        }

    }

    // 4. no positive numbers were found, which means

     the array contains all numbers 1..n

    return n + 1;

}

}