LeetCode 41 First Missing Positive

Tag: LeetCode Posted on 2021-05-25 10:32:48 Edited on 2021-05-25 19:29:00 Views: 55

https://leetcode.com/problems/first-missing-positive/

题目分析

要求 O(n) 的时间复杂度,O(1) 的空间复杂度。

题目让我们找出最小的缺失的正整数,其满足两个条件即可:

  1. 该数数组中没有;
  2. 该数前面的正整数数组中有。

由于不能对数组进行排序,我们得想办法存下一些信息来帮助我们判断以上两个条件。

简单想了一下,貌似不能分治,那就只好遍历咯?

我们设当前目标值为 t,即当前最小的缺失的正整数。

设想我们现在正在进行中间某步,现在有一个新的正整数值 x(非正整数直接忽略即可)需要处理:

  1. x < t,该值没有意义;
  2. x = t,条件一不再满足,如果 t+1 数组中不存在,则 t=t+1,否则的话一直加 1,直到找到一个不存在的值。
  3. x > t,当前目标值虽然还是目标值,但我们需要以某种方式标记 x 已经出现过。

其中情况 2 和 3 都要求我们能够查询某个值是否已经存在。

如果用 Hash 表来进行标记的话,唯一的问题是,我们只能有常数项个值。

看了下 Hint:

Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?

哦,我们或许可以用数组的前面部分来当 Hash 表来用? 假设中间某步为第 i 步(从 1 开始),t 一定满足:t<i

额,貌似不行啊。


时间已经过了很久了,爷决定屈服了。

高赞 #1

https://leetcode.com/problems/first-missing-positive/discuss/17080/Python-O(1)-space-O(n)-time-solution-with-explanation

实际上我们的 Hash 表有常数项个即可,因为目标值一定不会大于数组长度,所以说 Hash 表的项的数目最多不超过数组长度。

这样的话,直接用一个等长度的数组做 Hash 表即可。

是这一步分析出了问题:

如果用 Hash 表来进行标记的话,唯一的问题是,我们只能有常数项个值。

我们用 Hash 表来进行记录:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int res = 1;
        unordered_map<int,bool> store;
        for(auto num : nums) {
            if (num < res) continue;
            if (num > nums.size()) continue;
            if (num == res) {
                res++;
                while(store.find(res) != store.end()) res++;
            } else {
                store[num] = true;
            }
        }
        return res;
    }
};

104 ms & 66.4 MB

用 Hash 表来记录还是太浪费了。

换成数组:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int res = 1;
        vector<bool> store(nums.size()+1);
        for(auto num : nums) {
            if (num < res) continue;
            // We don't care num that large then nums.size()
            if (num > nums.size()) continue;
            if (num == res) {
                res++;
                // We have to make sure res is in a proper range.
                while(res < nums.size() + 1 && store[res]) res++;
            } else {
                store[num] = true;
            }
        }
        return res;
    }
};

96 ms & 66.3 MB

emmm,差别并不大。

高赞 #2

https://leetcode.com/problems/first-missing-positive/discuss/17071/My-short-c%2B%2B-solution-O(1)-space-and-O(n)-time

这个就太巧妙了,对我的实用价值不大,2333。

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for(int i = 0; i < n; ++ i)
            while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
                swap(A[i], A[A[i] - 1]);
        
        for(int i = 0; i < n; ++ i)
            if(A[i] != i + 1)
                return i + 1;
        
        return n + 1;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/