<reponame>ChiFire/legend_LeetCode<filename>040 First Missing Positive.py
"""
Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.
"""
__author__ = 'Danyang'
class Solution:
    def firstMissingPositive(self, A):
        """
        Bucket Sort without extra space
        O(n)

        Extra space is eliminated by using the array A itself as a storage

        :param A: a list of integers
        :return: an integer
        """
        if not A:
            return 1

        i = 0
        length = len(A)
        while i<length:
            current = A[i]
            if current<=0 or current>length or A[current-1]==current:  # out-of-range or in-place
                i += 1
            else:
                A[current-1], A[i] = current, A[current-1]   # go to the next iteration


        for i in xrange(length):
            if A[i]!=i+1:
                return i+1
        return A[-1]+1


if __name__=="__main__":
    assert Solution().firstMissingPositive([3,4,-1,1])==2
First Missing Positive.py
"""
Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.
"""
__author__ = 'Danyang'
class Solution:
    def firstMissingPositive(self, A):
        """
        Bucket Sort without extra space
        O(n)

        Extra space is eliminated by using the array A itself as a storage

        :param A: a list of integers
        :return: an integer
        """
        if not A:
            return 1

        i = 0
        length = len(A)
        while i<length:
            current = A[i]
            if current<=0 or current>length or A[current-1]==current:  # out-of-range or in-place
                i += 1
            else:
                A[current-1], A[i] = current, A[current-1]   # go to the next iteration


        for i in xrange(length):
            if A[i]!=i+1:
                return i+1
        return A[-1]+1


if __name__=="__main__":
    assert Solution().firstMissingPositive([3,4,-1,1])==2
Given an unsorted integer array, find the first missing positive integer.
 
 For example,
 Given [1,2,0] return 3,
 and [3,4,-1,1] return 2.
 
 Your algorithm should run in O(n) time and uses constant space. Bucket Sort without extra space
         O(n)
 
         Extra space is eliminated by using the array A itself as a storage
 
         :param A: a list of integers
         :return: an integer # out-of-range or in-place # go to the next iteration