41. 缺失的第一个正数 + 哈希表 + 思维

41. 缺失的第一个正数

LeetCode_41

题目描述

41. 缺失的第一个正数 + 哈希表 + 思维

题解分析

  1. 利用哈希表的思想,但是不是使用HashMap。
  2. 使用整个数组作为哈希桶,每个nums[i]的数字作为索引下标,将其置为负数表示该位置有数字。
  3. 需要注意最后返回的是n+1表示原来数组中包含所有1-n的数字。

方法一:哈希思想

class Solution {
    public int firstMissingPositive(int[] nums) {
        //模仿哈希表的原理,使用原来的数组实现hash的目的
        int n = nums.length;

        //首先小于等于0的数都统一设置为n+1,因为题目要求的是第一个缺失的正数,这个整数一定从1开始
        for(int i=0; i<n; i++){
            if(nums[i] <= 0)
                nums[i] = n + 1;
        }

        //接着,将hash的位置置为相应的负数,实现hash的目的
        for(int i=0; i<n; i++){
            int num = Math.abs(nums[i]);//注意这里需要使用绝对值,因为后续可能会将位置上的数字指定为负数
            if(num <= n){
                nums[num - 1] = -Math.abs(nums[num - 1]);//将相应位置置为负数表示这个位置已经有数字了
            }
        }
        //最后,第一个大于0的位置就是最小正数
        for(int i=0; i<n; i++){
            if(nums[i] > 0){
                return i+1;
            }
        }
        return n + 1;//这里需要注意的是返回最大值,能走到这步说明数组中的元素都是从1到n连续的
    }
}

方法二:置换法

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //置换法
        for(int i=0; i<n; i++){
            while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]){//注意这里有一个循环,因为交换位置后的nums[i]有可能也处在1-n之间,需要再次转换
                int temp = nums[nums[i] - 1];
                nums[nums[i] -1] = nums[i];
                nums[i] = temp;
            }
        }
        for(int i=0; i<n; i++){
            if(nums[i] != i+1)
                return i+1;
        }
        return n + 1;//这里需要注意的是返回最大值,能走到这步说明数组中的元素都是从1到n连续的
    }
}
上一篇:『动善时』JMeter基础 — 41、使用JMeter连接数据库(MySQL)


下一篇:当前类没有默认构造函数,但成员对象有默认构造函数(整理自深度探索C++对象模型 的41页)