1、前言

2、思路

这道题如果使用 O(n) 的时间复杂度，但是 O(n) 的空间复杂度很好解决，使用 hashset 即可。如果使用 O(NlogN) 但是 O(1) 的时间复杂度也很好解决，使用二分查找即可。hashset 的思路跟二分查找差不多，只是 hashset 存储了所有数，并且使用 hash 查找；而二分查找使用原数组存储，每次使用二分查找而已。

但是这两种做法都不满足题目的要求。

我们可以以原数组进行修改，将数组中的元素挪到它该去的地方。比如，如果数组中的元素为1，那么就挪到 0；元素是 i，就挪到 i - 1 的位置。然后到最后我们可以发现，那些 nums[i] != i + 1 的位置，就是需要查找的值。挪数组的时候，不能覆盖原来的，所以需要将数组 nums[i] - 1 的位置与 i 的位置进行替换。替换的过程中，如果 nums[nums[i] - 1] 与 nums[i] 相等，则要跳出来，要不然是个死循环。

有人说，上述思路我不可以一次循环吗？循环一次然后交换即可，不需要在 for 循环中用 while 直到不能替换位置。答案是不能，就以[3, 4, -1, 1] 为例，一次循环后 [-1, 1, 3, 4]，可以看到1并没有移到正确的位置。

3、代码

二分查找：

class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }

        Arrays.sort(nums);

        for(int i = 1; i <= nums.length; i++){
            int index = binarySearch(nums, i);
            if(index == -1){
                return i;
            }
        }

        return nums.length + 1;
    }

    private int binarySearch(int[] nums, int target){
        int left = 0, right = nums.length - 1;

        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }

        return -1;
    }
}

原地修改：

class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }

        int len = nums.length;
        for(int i = 0; i < nums.length; i++){
            while(nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]){
                swap(nums, i, nums[i] - 1);
            }
        }

        for(int i = 0; i < len; i++){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }

        return len + 1;
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}