缺失的第一个正整数

/**

 * 置换

 * 恢复数组，数组应当有 [1, 2, ..., N] 的形式，

 * 但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。

 * 以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 2。

 *

 * @param nums

 * @return

 */

public static int firstMissingPositive2(int[] nums) {

    int length = nums.length;

    for (int i = 0; i < length; i++){

        // 循环交换，直到当前位置为当前值

        while (nums[i] <= length && nums[i] > 0 && nums[nums[i] - 1] != nums[i]){

            int temp = nums[nums[i] - 1];

            nums[nums[i] - 1] = nums[i];

            nums[i] = temp;

        }

    }

    int result = 1;

    for (int i = 0; i < length; i++){

        if (nums[i] != result) break;

        result++;

    }

    return result;

}

/**

 * 哈希表

 * 我们将数组中所有小于等于 0 的数修改为 N+1；

 *

 * 我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 |x|，

 * 其中 || 为绝对值符号。如果 |x|∈[1,N]，那么我们给数组中的第 |x|-1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；

 *

 * 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。

 *

 * @param nums

 * @return

 */

public static int firstMissingPositive3(int[] nums) {

    int length = nums.length;

    for (int i = 0; i < length; i++){

        if (nums[i] <= 0) nums[i] = length + 1;

    }

    for (int i = 0; i < length; i++){

        int index = Math.abs(nums[i]);

        if (index <= length){

            nums[index - 1] = -Math.abs(nums[index - 1]);

        }

    }

    for (int i = 0; i < length; i++) {

        if (nums[i] > 0){

            return i + 1;

        }

    }

    return length + 1;

}