leetcode First Missing Positive

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.

题目地址：leetcode First Missing Positive

题目大意: 给定一些数，找出第一个没有出现的正数。要求时间复杂度O(n) 空间复杂度O(1)

思路：

将值为i的数放在下标i-1的位置，即：nums[i]存放的应该是i+1这个数。

因此，若以下条件均满足

i + 1 != nums[i]
0 < nums[i] <= len(nums)
nums[i] != nums[nums[i] - 1]

则可以交换。

第一个条件说明当前位置不满足条件。

第三个条件说明nums[i]应该放在nums[nums[i] - 1]这个位置上，若那个位置不是nums[i]则交换

第二个条件保证第三个条件的下标不会越界。

在交换完之后，扫描数组，若nums[i] != i + 1则返回i+ 1，若都满足说明缺的是len(nums) + 1

为什么是对的？

因为我们把值为x的放入了x-1的位置，那么1放入0的位置，len(nums) 放入len(nums) -1的位置。

如果存在值为x的数，那么上面的交换过程保证了位置x-1放置了x。

下面的代码中，第一个条件和第三个合并了，只需要第三个条件即可。（推导一下很显然的,若i + 1 == nums[i]，则 nums[i] == nums[i + 1 - 1]）

C++

class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		for (int i = 0; i < nums.size(); ++i) 
			while(0 < nums[i] && nums[i] <= nums.size() && nums[i] != nums[nums[i] - 1])
				swap(nums[i], nums[nums[i] - 1]);
		
		for (int i = 0; i < nums.size(); ++i)
			if (nums[i] != (i + 1))
				return i + 1;
		return nums.size() + 1;
	}
};

Python

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
            while 0 < nums[i] <= len(nums) and nums[i] != nums[nums[i] - 1]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
                
        for i in range(len(nums)):
            if i + 1 != nums[i]:
                return i + 1
        return len(nums) + 1

ps：

以前被py的交换坑了一把，写成如下的第九行就进入死循环。

最好是用上面的临时变量

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

本文是leetcode如下的题解

41. First Missing Positive

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/