缺失的第一个正数 - LeetCode 热题 17

大家好！我是曾续缘😁

今天是《LeetCode 热题 100》系列

发车第 17 天

普通数组第 5 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

缺失的第一个正数

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

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

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

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

难度：💝💝💝

解题方法

假设数组长度为$N$,答案一定是$1\sim N+1$范围中的某个数, 一种$N+1$种可能, 我们可以判断$N$种可能, 使用排除法判断最后一种.
平时我们使用数组作为哈希表, 能哈希的个数就是数组的长度,这里数组长度为$N$,正好可以判断$N$种可能(判断$1\sim N$),还有一个问题就是哈希时我们需要在哈希槽里做标记,这会改变原本数组里的值,有什么办法可以将做标记和原本的数平行开来,互不影响呢?

1. 使用位运算, 根据$N\le 5\ast 10^5$的范围, 将数组里不可能为答案的数使用某一个高位标志, 再使用另一个不同的高位来作为哈希标志.
2. 使用正负来作为哈希标志，这就需要保证原数组没有负数出现，考虑到答案为正数, 将数组里的负数改为不需要做哈希的数(大于$N$), 将对应的哈希槽的值改为负数作为标志, 将数组里的值的绝对值作为需要哈希的值,这样就忽略了负数对数组的影响, 对于大于$N$的数不需要做哈希.

Code

class Solution { // 位运算
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int impossible = 1 << 28, mask = 1 << 29;
        for(int i = 0; i < n; i++){
            if(nums[i] <= 0 || nums[i] > n){
                nums[i] |= impossible;
                nums[i] &= ~mask;
            }
        }
        for(int i = 0; i < n; i++){
            if((nums[i] & impossible) > 0){
                continue;
            }
            nums[(nums[i] & ~mask) - 1] |= mask;
        }
        for(int i = 0; i < n; i++){
            if((nums[i] & mask) == 0){
                return i + 1;
            }
        }
        return n + 1;
    }
}
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            if(nums[i] <= 0){
                nums[i] = n + 1;
            }
        }
        for(int i = 0; i < n; i++){
            int num = Math.abs(nums[i]);
            if(num <= n){
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for(int i = 0; i < n; i++){
            if(nums[i] > 0){
                return i + 1;
            }
        }
        return n + 1;
    }
}