41. First Missing Positive

2019-04-19

41. First Missing Positive

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

Example 1:

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

Example 2:

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

Example 3:

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

Note:

Your algorithm should run in _O_(_n_) time and uses constant extra space.

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n, i = len(nums), 0
        if n == 0: return 1

        while i < n:
            # 获取当前位置的数据
            w = nums[i] - 1  
            # 0 < nums[i] <= n 判断是否出界
            if 0 < nums[i] <= n and nums[i] != nums[w]:
                # nums[i] != nums[w] 如果相等或者是本身就没必要替换了，避免死循环
                nums[i], nums[w] = nums[w], nums[i]      
            # 当前位置上的数，没有找到合适的位置，进行下一个位置
            else:
                i += 1  
         # 遍历返回
        for i in range(n):
            if i + 1 != nums[i]:
                return i + 1
        return n + 1
-->