41. 缺失的第一个正数 - 力扣（LeetCode）

发表于 更新于 分类于 阅读次数： Disqus：

题目描述

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3: 输入: [7,8,9,11,12] 输出: 1 说明: 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

题解

看到时间复杂度为[latex]o(n)[/latex]，空间复杂度为[latex]o(1)[/latex]。之前抱有哈希表的想法顿时烟消云散。 然后查看第一个提示，假如在非常量的情况下，你会怎么做？能否将这种思路应用在常量空间中。 恕我愚钝，写完非常量下的做法后，还是没有任何思路，只能查看官方题解。 大体思路如下： 对于nums数组，其缺失的第一个正数只可能出现在1-nums.size()+1中。而对于负数和0并不影响结果。 1. 首先判断当前数组中是否存在1，若没有1，则缺失的第一个正数就是1；如果存在，则进行第二步。 2. 将负数，0和大于nums.size()变成1。 3. 借助哈希标记的思路，这里采用拿自己当bitmap的绝妙思路，如果i出现，则改变nums[i]的符号，如果nums.size()出现则改变nums[0]的符号，重复元素只改变一次符号。 4. 首个出现的正元素其下标为本题解，均为负，则解为nums.size() + 1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int>my_set;
        int res;
        for(int i = 0; i < nums.size(); ++i){//哈希表标记
            my_set.insert(nums[i]);
        }
        for(int i = 1; i <= nums.size() + 1; ++i){
            if(my_set.find(i) == my_set.end()){
                res = i;
                break;
            }
        }
        return res;
    }
};

执行结果

官方题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        bool flag = false;
        int idx = 1;
        for(int i = 0; i < nums.size(); ++i){//判断是否存在1
            if(nums[i] == 1){
                flag = true;
                break;
            }
        }
        if(!flag){
            return 1;
        }
        else{
            for(int i = 0; i < nums.size(); ++i){//将非正数和大于nums.size()的数替换为1
                if(nums[i] <= 0  nums[i] > nums.size()){
                    nums[i] = 1;
                }
            }
            for(int i = 0; i <nums.size(); ++i){//符号标记
                idx = abs(nums[i]);
                if(idx == nums.size() && nums[0] > 0){//仅为正的时候才改变符号是为了保证修改一次。
                    nums[0] = -nums[0];
                }
                else if(idx != nums.size() && nums[idx] > 0){
                    nums[idx] = -nums[idx];
                }
            }
            for(int i = 1; i < nums.size(); ++i){
                if(nums[i] > 0){
                    return i;
                }
            }
            if(nums[0] > 0){//如果后面全为负，nums[0]为正,则返回nums.size()
                return nums.size();
            }
            else{//如果都为负，则返回nums.size() + 1
                return nums.size() + 1;
            }
        }
    }
};

执行结果