Dx's Tech Notes

5._找到第一个正整数

3 min read

  • 2.25

    • 如果题目不要求正整数，把 0 也包括在内，就是 i 与 nums【i】的对比，而不是 i 与 nums【i】-1 的对比
    • 记得在 while 循环中，判断 nums【i】是否在数组范围内
    • 找到 i 时，返回的是 i+1 哦，因为不包括 0

  • 2.10

    • nums[i]与 nums[nums[i]-1]的比较
    • 注意 for 里会 while 循环确保当前nums[i]的位置是对的
class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i=0;i<nums.length;i++){
            while(nums[i]>0&&nums[i]<=nums.length&&nums[i]!=nums[nums[i]-1]){
                swap(nums,i,nums[i]-1);
            }
        }
        for(int i=0;i<nums.length;i++){
            if(i!=nums[i]-1){
                return i+1;
            }
        }
        return nums.length+1;
    }
    public void swap(int[] nums,int l,int r){
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}
如果使用 while (死磕到底)
同样看 i = 0，当前数字是 3。

第一轮 while：

nums[0] 是 3，位置不对。

交换 3 和索引 2 上的 2。

数组变为：[2, 1, 3]

注意！while 循环还没停！

代码再次检查 while 条件：现在的 nums[0] 是 2。

2 应该在索引 1 吗？不在。它现在在索引 0。

继续交换：把 2 和索引 1 上的 1 交换。

数组变为：[1, 2, 3]

第三轮 while：

现在的 nums[0] 是 1。

1 应该在索引 0 吗？是的 (nums[0] == 0 + 1)。

条件不满足，退出循环。

指针移动：i++。
  • 1.24
    • 因为是正整数，所以 i 放在 数组的i-1的位置 nums[nums[i] - 1] != nums[i] 找到第一个不合规则的数“ums[i] != i + 1`
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
 
        // 1. 原地哈希：把数字放到该去的位置上
        for (int i = 0; i < n; i++) {
            // 条件解析：
            // nums[i] > 0 : 只管正数
            // nums[i] <= n : 太大的数不用管，比如 n=4, 来了个 100，随它去
            // nums[nums[i] - 1] != nums[i] : 目标位置上的数还不正确，才需要交换
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // 交换 nums[i] 和 nums[nums[i] - 1]
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
 
        // 2. 找第一个不符合规则的坑
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1; // 找到了，下标 i 应该放 i+1 的
            }
        }
 
        // 3. 如果萝卜全在坑里，说明 1 到 n 都在，缺失的是 n + 1
        return n + 1;
    }
}

Graph View