来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位华为鸿蒙的员工说，在华为想休息一天好难。评论区有位脉友说基本没见过华为有人请假，因为大部分人都签了奋斗者协议，删除了年假和法定假期，请假会影响考勤系数，还要扣双倍工资。如果真是这样的话，请假的成本真是太高了，随便请个一两天，几千块就没了。还有一位也在鸿蒙项目组的脉友说，bug贼多，基本没有休息的。直接把正打算学鸿蒙的脉友给劝退了。
不知道华为是不是真的这样，有知情的小伙伴可以评论区分享一下。
不少同学对虎哥的视频非常认可，直接成为了原始粉。
言归正传，今天我们来分享一道华为的面试原题「缺失的第一个正数」。
题目描述
给你一个未排序的整数数组 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)。
今天的分享就到这里，希望大家能有所收获！
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
