leetcode 热题 100_缺失的第一个正数

题解一：

        正负模拟哈希：偏技巧类的题目，在无法使用额外空间的情况下，只能在原数组中做出类似哈希表的模拟。除去数值，我们还可以用正负来表示下标值的出现情况。首先，数组中存在正负数和0，而负数和0对结果是没有影响的，我们将它们设置为一个较大的正数0x3f3f3f3f，如此，当前数组中就只存在正整数。

设想一下，没有出现的最小的正整数可能的值，一定是在[1,nums.length+1]中的，原因是数组最多只能有nums.length个正整数。因此下一步我们将处于这个范围内出现过的值，nums[值-1]设置为负数，来表示这个值已经出现过了。这里需要注意三点：第一，[1,nums.length+1]中只有[1,nums.length]可以用下标表示，而存储结果的值result可以初始化为nums.length+1。第二，我们需要用绝对值来表示这些正整数，因为先出现的值可能会将后出现的值设置为负数。第三，使用乘-1的方式，出现偶数次的数值仍然会被判断为未出现过，因此必须加上判断语句。

最后我们遍历数组，找到的第一个正数，对应的下标+1就是未出现过的最小正整数。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int result = nums.length + 1;

        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) nums[i] = 0x3f3f3f3f;
        }

        for (int i = 0; i < n; i++) {
            int temp = Math.abs(nums[i]);
            if (temp <= n && nums[temp - 1] > 0) nums[temp - 1] *= -1;
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                result = i + 1;
                break;
            }
        }
        return result;
    }
}