【每日算法Day 75】字节跳动面试题：手撕困难题，看过我Day 71的人都会做了！...

题目链接

LeetCode 41. 缺失的第一个正数[1]

题目描述

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

示例1

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

示例2

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

示例3

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

说明：

• 你的算法的时间复杂度应为

  ，并且只能使用常数级别的空间。

题解

如果之前一直坚持看我题解的同学，应该前几天刚看过下面这道题：

​​【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法​​

韦阳的博客：【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法[2]

知乎专栏：【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法[3]

那道题是要求

到

中缺失的两个数，于是我们开辟一个大小为

回到本题，我们要寻找的是第一个缺失的正整数。其实问题的本质是一样的，如果数组的长度是

，那么最多只能填充

到

这

个正整数，所以缺失的正整数一定小于等于

那么我们把小于等于

或者大于

的数全部赋值为

，因为它们是多少不要紧，不影响最后的结果。然后和上面题目方法一样，用原地算法，把每个数字放入对应下标的位置。最后从左到右扫描一遍数组，如果发现有位置是

，那么第一个缺失的正数就是它了。如果扫描完

到

发现全都在，那么第一个缺失的就是

因为我们要保存

到

时间复杂度是

，空间复杂度是

代码

c++

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

参考资料

[1]

LeetCode 41. 缺失的第一个正数: ​​https://leetcode-cn.com/problems/first-missing-positive/​​

[2]

韦阳的博客：【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法: ​​https://godweiyang.com/2020/03/16/leetcode-interview-17-19/​​

[3]

知乎专栏：【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法: ​​https://zhuanlan.zhihu.com/p/113534188​​

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~