First Missing Positive

Given an unsorted integer array, find the first missing positive integer.Have you met this question in a real interview? Yes

Example

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

Challenge

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

既然不能建立新的数组，那么我们只能覆盖原有数组，我们的思路是把1放在数组第一个位置nums[0]，2放在第二个位置nums[1]，即需要把nums[i]放在nums[nums[i] - 1]上，那么我们遍历整个数组，如果nums[i] != i + 1, 而nums[i]为整数且不大于n，另外nums[i]不等于nums[nums[i] - 1]的话，我们将两者位置调换，如果不满足上述条件直接跳过，最后我们再遍历一遍数组，如果对应位置上的数不正确则返回正确的数，代码如下：

public class Solution {
    /**
     * @param A: An array of integers
     * @return: An integer
     */
    public int firstMissingPositive(int[] A) {
        // write your code here
        if(A == null || A.length == 0){
            return 1;
        } 
        
        for (int i =0; i < A.length ;++i ){
            while(A[i] > 0 && A[i] <= A.length && A[i] != i+1){
                int tmp = A[A[i]-1];
                if(tmp == A[i]){
                    break;
                }
                
                A[A[i]-1] = A[i];
                A[i] = tmp;
            }
            
        } 
        
        for(int i = 0; i < A.length; i++){
            if(A[i] != i+1){
                return i+1;
            }
        }
        
        return A.length + 1;
    }
}

好理解的解法

time o(n),space o(1)

class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0)
            return 1;
        
        for(int i = 0; i < nums.length; i++){
            while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){
                int tmp = nums[nums[i] - 1];
                nums[nums[i] -1] = nums[i];
                nums[i] = tmp;
            }
        }
        
        for(int i = 0; i < nums.length;i++){
            if(nums[i] != i+1){
                return i+1;
            }
        }
        
        return nums.length+1;
    }
}