大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位华为鸿蒙的员工说，在华为想休息一天好难。评论区有位脉友说基本没见过华为有人请假，因为大部分人都签了奋斗者协议，删除了年假和法定假期，请假会影响考勤系数，还要扣双倍工资。如果真是这样的话，请假的成本真是太高了，随便请个一两天，几千块就没了。还有一位也在鸿蒙项目组的脉友说，bug贼多，基本没有休息的。直接把正打算学鸿蒙的脉友给劝退了。
不知道华为是不是真的这样，有知情的小伙伴可以评论区分享一下。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道华为的面试原题「缺失的第一个正数」。
题目描述
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
举个例子：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
思路解析
根据题意我们可以知道，如果数组的大小为n，那么数组中的正整数的范围为[1, n]。比较简单的方法是把数组中的元素放到hashset中，然后依次从小到大去hashset中寻找区间[1, n]中的正整数，区间[1, n]中第一个不存在于hashset中的正整数，就是缺失的第一个正数。这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)， 其中 n 为数组nums的长度。
我们可以通过使用原数组替代hashset，这样就不需要使用额外的空间，可以把时间复杂度做到 O(1)。下面我来介绍一下如何使用原数组替代hashset。
因为数组中的正整数的范围为[1, n]，我们可以对数组0～n-1位置上的元素稍加标记，来代表正整数1～n是否存在数组中。比如数组中存在正整数2，我们就把nums[2 - 1]标记成负数，后面根据nums[2 - 1]的符号判断2是否存在数组中， 使用nums[2 - 1]的时候取绝对值就可以。这里存在一个问题，数组中可能本来就存在负数，还有可能存在0。
针对数组中本来就可能存在负数，我们可以一开始就把数组中的负数改成
0，这不会影响整体逻辑。对于数组中存在正整数
i且nums[i - 1] == 0，标记负0还是等于0，无法区分正整数i是否存在，我们可以把nums[i - 1]设置成绝对值在区间[1, n]以外的负数-(n + 1)，这样再次遍历到nums[i - 1]时，nums[i - 1]的绝对值减一为n超出数组索引的范围0~n-1，不需要修改数组中元素的符号，也不会影响整体逻辑。
假设nums = [1,2,0,-1]，我们给出整个算法的步骤：
把原数组 nums中的负数全部变成0，这样整个数组就只包含正整数和0。
遍历数组，对元素 nums[i]取绝对值，如果元素的绝对值|nums[i]|在[1, n]之间且nums[|nums[i]|]不等于0，就把nums[|nums[i]|]变成负数-nums[|nums[i]|]。如果元素的绝对值|nums[i]|在[1, n]之间且nums[|nums[i]|]等于0，就把nums[|nums[i]|]变成-(n + 1)。
重新遍历数组，第一个不为负数的元素对应的索引的值加 1，就是缺失的第一个正整数。
下面我们给出c++和python的两种代码实现。
c++代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
//把小于0的元素全部变成0
if (nums[i] < 0) {
nums[i] = 0;
}
}
for (int i = 0; i < nums.size(); ++i) {
//取元素的绝对值
int val = nums[i];
if (val < 0) {
val = (-1 * val);
}
if (val >= 1 && val <= nums.size()) {
//如果val存在数组中且nums[vals - 1]的值大于0，则把nums[vals - 1]的值置为负数
if (nums[val - 1] > 0) {
nums[val - 1] = (-1 * nums[val - 1]);
//如果val存在数组中且nums[vals - 1]的值等于0，则把nums[vals - 1]的值置为一个不影响整体逻辑的负数
} else if (nums[val - 1] == 0) {
nums[val - 1] = (-1 * (nums.size() + 1));
}
}
}
for (int i = 1; i <= nums.size(); ++i) {
//数组中从左到右第一个正数的索引就是缺失的那个正数
if (nums[i - 1] >= 0) {
return i;
}
}
//如果数组中全是正数就返回最大的正数+1
return nums.size() + 1;
}
};
python代码
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
for i in range(len(nums)):
# 把小于0的元素全部变成0
if nums[i] < 0:
nums[i] = 0
for i in range(len(nums)):
# 取元素的绝对值
val = nums[i]
if val < 0:
val = (-1 * val)
if 1 <= val <= len(nums):
# 如果val存在数组中且nums[vals - 1]的值大于0，则把nums[vals - 1]的值置为负数
if nums[val - 1] > 0:
nums[val - 1] = (-1 * nums[val - 1])
# 如果val存在数组中且nums[vals - 1]的值等于0，则把nums[vals - 1]的值置为一个不影响整体逻辑的负数
elif nums[val - 1] == 0:
nums[val - 1] = (-1 * (len(nums) + 1))
for i in range(1, len(nums) + 1):
# 数组中从左到右第一个正数的索引就是缺失的那个正数
if nums[i - 1] >= 0:
return i
# 如果数组中全是正数就返回最大的正数+1
return len(nums) + 1
复杂度分析
时间复杂度： 需要遍历一遍数组，时间复杂度为 O(n)，其中n为数组中元素的个数。
空间复杂度： 整个操作都是基于原数组的，没有使用到额外的空间，所以空间复杂度为 O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
