LeetCode刷题 【41】缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

 

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

 

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

\n

题解

如果不限条件的话，额外申请一个hash表，遍历数组，记录每个在遍历过程中遇到的数字，遍历完成后，再从1开始自增到hash中查询，第一个查不到的即为结果。

代码简单

class SolutionByHashSet {
        Set<Integer> set;
        public int firstMissingPositive(int[] nums) {
            set = new HashSet<>();
            for (int num : nums) {
                if (num>=0 && num<=num){
                    set.add(num);
                }
            }
            for (int i = 1; i <= nums.length; i++) {
                if (!set.contains(i)){
                    return i;
                }
            }
            return nums.length+1;
        }
    }

但是题目要求，常数级别额外空间，就需要再想想了，题目提供的是数组，而数组组和连续正数相关的话，自然会想到数组索引下标，那么依次遍历，把对应的值放到对应下标位置上是不是可行呢？不过不同的是，把数字1放在下标0的位置，数字2，放在下标1的位置……这样的方法。

拿用例想一下试试【3,4,-1,1】

• 下标0位置得到数字3，那么3应该把他放到下标2的位置，所以两个下标上面的值进行交换得到新的数组【-1,4,3,1】
• 此时下标0位置的值为-1，-1这个值找不到对应的下标下标上去放置，那么我们再去处理下标1位置的值
• 到了下标1之后，这个位置的值是4，把它和对应下标3位置的值交换，得到新的排序【-1,1,3,4】。
• 此时下标1位置的值为1，继续把这个值和对应下标0的位置值交换，新的数组排序是【1,-1,3,4】
• 此时下标1位置的值为-1，那么去处理下一个下标位置上的值，后面略过，因为对应位置的值都是对应的

最终再从头开始遍历一遍判断对应下标置上的值是否是+1的数字

代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i]!= i+1){
                //终止条件
                //当前位置上的值再不能对应到nums的索引0到nums.length-1上
                //即，nums[i]的值在1-nums.length之间，包含区间
                if (nums[i] < 1 || nums[i]>nums.length){
                    break;
                }
                //有重复值
                if (nums[i] == nums[nums[i]-1]){
                    break;
                }
                swap(nums,i,nums[i]-1);
                //当前位置的值等于对应值，即nums[i]== i+1这个发生在交换之后
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]!= i+1){
                return i+1;
            }
        }
        return nums.length+1;
    }


    private void swap(int[] nums, int index1, int index2){
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}

最后提交的时候还是漏了一个里面有重复值的情况。于是再次加了个

if (nums[i] == nums[nums[i]-1]){
    break;
}