对于一个长度为 N
的数组,其中没有出现的最小正整数只能在[1,N+1]
中。这是因为如果[1,N]
都出现了,那么答案是N+1
,否则答案是[1,N]
中没有出现的最小正整数。
这样一来,我们将所有在[1,N]
范围内的数放入哈希表,也可以得到最终的答案。而给定的数组恰好长度为N
。
这让我们有了一种将数组设计成哈希表的思路:我们对数组进行遍历,对于遍历到的数x
,如果它在[1,N]
的范围内,那么就将数组中的第x−1
个位置(注意:数组下标从0
开始)打上「标记」。在遍历结束之后,如果所有的位置都被打上了标记,那么答案是N+1
,否则答案是最小的没有打上标记的位置加1
。
那么如何设计这个「标记」呢?由于数组中的数没有任何限制,因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质:由于我们只在意[1,N]中的数,因此我们可以先对数组进行遍历,把不在[1,N]范围内的数修改成任意一个大于N的数(例如 N+1)。这样一来,数组中的所有数就都是正数了,因此我们就可以将「标记」表示为「负号」。
算法的流程如下:
-
我们将数组中所有小于等于
0
的数修改为N+1
; -
我们遍历数组中的每一个数
x
,它可能已经被打了标记,因此原本对应的数为∣x∣
。如果∣x∣∈[1,N]
,那么我们给数组中的第∣x∣−1
个位置的数添加一个负号。注意如果它已经有负号,不需要重复添加; -
在遍历完成之后,如果数组中的每一个数都是负数,那么答案是
N+1
,否则答案是第一个正数的位置加1
。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for(auto& num : nums)
if(num <= 0)
num = n + 1;
for(int i = 0; i < n; i ++)
{
int num = abs(nums[i]);
if(num <= n)
nums[num - 1] = - abs(nums[num - 1]);
}
for(int i = 0; i < n ; i++)
if(nums[i] > 0)
return i + 1;
return n + 1;
}
};
标签:遍历,第一个,标记,nums,数组,正数,缺失,答案
From: https://www.cnblogs.com/bothgone/p/17300901.html