【LeetCode】41.缺失的第一个数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

思路：哈希表

对于一个长度为N的数组，其中没有出现的最小正整数只能在[1，N+1]中，因为如果[1，N]都出现了，那么答案是N+1，否则答案就是[1，N]中没有出现的最小正整数。将所有在[1，N]范围内的数放在哈希表，就可得到最终答案。

算法过程：

• 将数组中所有小于等于0的数修改为N+1;
• 遍历数组中的每一个数x，可能已经被打了标记（表示为负号），因此原本对应的数为|x|(||为绝对值符号),如果|x|属于[1,N]范围，那么就给数组中的第|x|-1个位置的数添加一个负号。
• 遍历完成后，如果数组中的每一个数都是负数，那么答案是N+1，否则答案是第一个正数的位置加1.

代码：

class Solution {
    // 哈希表法
    public int firstMissingPositive(int[] nums) {
        // 首先将数组中所有负数变为N+1（N为数组的长度）
        int len = nums.length;
        for(int i=0; i<nums.length; i++){
            if(nums[i] <= 0){
                nums[i] = len+1;
            }
        }
        // 遍历数组，如果x在[1，N]范围内，则打上标记，本题【标记】表示为【负号】
        for(int i=0; i<nums.length; i++){
            int num = Math.abs(nums[i]);
            if(num <= len){
                nums[num-1] = -Math.abs(nums[num-1]);
            }
        }

        // 遍历数组，第一个正数位置为最终答案，如果全为负数，则答案为N+1；
        for(int i=0; i<nums.length; i++){
            if(nums[i] > 0)
                return i+1;
        }
        return len+1;
    }
}