First Missing Integer

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

Given [1,2,0] return 3,

[3,4,-1,1] return 2,

[-8, -7, -6] returns 1

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

思路:

将positive integer v都swap到index v - 1，然后从左往右scan array，第一个index i != i + 1的数，i + 1即是missing integer。
比如说[1, 2, 0] -> [1, 2, 0]，index 2即是missing integer，所以返回3
[3,4,-1,1] -> [-1, 4, 3, 1] -> [-1, 1, 3, 4] -> [1, -1, 3, 4]，index 1是missing number，返回2
[-8, -7, -6]，index 0是missing number，返回1

Solution:

Time: O(n)，因为每个数最多swap一次
Space: O(1)

public class Solution {
    public int firstMissingPositive(ArrayList<Integer> A) {
        int n = A.size();
        for (int i = 0; i < n; i ++) {
            int val = A.get(i);
            int idealVal = i + 1;
            int swapToIndex = val - 1;
            while (val != idealVal && swapToIndex >= 0 && swapToIndex < n && val != A.get(swapToIndex)) {
                swap(A, i, swapToIndex);
                val = A.get(i);
                swapToIndex = val - 1;
            }
        }
        // System.out.println(A.toString());
        for (int i = 0; i < n; i ++) {
            int idealVal = i + 1;
            if (A.get(i) != idealVal) {
                return idealVal;
            }
        }
        return n + 1;
    }
    
    private void swap(ArrayList<Integer> A, int i, int j) {
        int temp = A.get(i);
        A.set(i, A.get(j));
        A.set(j, temp);
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        for (int i = 0; i < nums.length; i ++) {
            int idealVal = i + 1;
            int swapToIndex = nums[i] - 1;
            while (nums[i] != idealVal && swapToIndex >= 0 && swapToIndex < nums.length && nums[i] != nums[swapToIndex]) {
                swap(nums, i, swapToIndex);
                swapToIndex = nums[i] - 1;
            }
        }
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
    
    private void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}