🌕🌕 41. 缺失的第一个正数

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 思路：
        // 对于 len 长度的数组，没有出现的最小正整数区间∈ [1, len + 1]
        // 即，如果在数组中，1 从没有出现过，那么 res = 1
        // 如果数组中，[1, len] 全部均出现，那么 res = len + 1
        // 现在要做的就是，遍历数组元素，
        // 如果 元素 i ∈ [1, len] ，那么可以将数组的 (i - 1) 下标做一个标记
        // 减一是为了让 数组下标[0, len - 1] 映射到 [1, len + 1] 
        // 表示该下标处值已经存在
        // 最后再遍历一次数组，哪个位置没有做标记，则说明这个是缺失的最小正整数
        // 问题在于：
        // 如何不占用额外空间，对数组做标记，同时还不能对数组该处的值做出改变，从而影响对该处值的判断？
        // 可以通过对该下标的值添加 负号 作为标记，
        // 如果要这样做，那么就需要保证遍历开始前，所有元素值本身的负号不能对数组产生影响
        // 所以需要提前遍历一次，对数组元素进行预处理
        // 将所有的负号元素，它肯定不在所需正数范围内，因此可以取一个区间外的正数值做替换，对结果无影响
        int len = nums.length;
        // 初次遍历，数据预处理
        for(int i = 0; i < len; i ++) {
            if(nums[i] >= 1 && nums[i] <= len) {
                continue;
            } else {
                if(nums[i] <= 0) {
                    nums[i] = len + 1;
                } else {
                    nums[i] = len + 1;
                }
            }
        }
        // 再次遍历，对满足条件的值，在对应下标处做标记
        for(int i = 0; i < len; i ++) {
            int cur = Math.abs(nums[i]); // 去掉负号影响，防止前面的数对应的就是该处下标，将其添加了负号
            if(cur >= 1 && cur <= len) {
                int index = cur - 1; // 理应给 index 处的值打上负号标记
                if(nums[index] > 0) {
                    nums[index] = -nums[index]; // 确保之前没有相同的值给该处下标已经做过标记
                }
            }
        }
        // 最后遍历，找到 res
        for(int i = 0; i < len; i ++) {
            if(nums[i] < 0) {
                continue;
            } else {
                return i + 1;
            }
        }
        // 如果都出现过，则
        return len + 1;
    }
}

---

输出