First Missing Positive

原题链接

Given an unsorted integer array, find the smallest missing positive integer

Input: [3,4,-1,1]
Output: 2

Note:
Your algorithm should run in O(n) time and uses constant extra space.

题意:给定一个未排序的数组,找到不在数组中的最小正整数

首先要明确一点,缺失的最小正整数一定在[1, n+1]范围内(不解释)

做法一:打表(No Good)

题目要求使用常量额外空间,那我就开了一个尽量大的数组(赌一波数据量)打表,结果数据量果然不大,当然如果n足够大,此方法行不通

代码如下:

做法二:一个萝卜一个坑

经典思路了,为每个数找到应该在的坑($num[i] = i+1(i\in[0, n-1])$),如果某个坑没有相应的数,说明该数缺失了,注意交换前判断是否有重复数防止陷入死循环

代码如下:

做法三:In-place使用-1标记

也是经典思路,在不使用额外空间的条件下,直接用-1在数组in-place打标记,有效性在于既做了标记又不影响元素本身的数值。

首先遍历一遍数组,将所有的负数及大于$n(n = nums.size())$的数全部设置为n+1,然后再遍历,将下标为 当前元素值的绝对值对n取模 的元素*(-1),同样要防止重复出现偶数次的数字(如果该元素是否已经小于0,则不对其再*(-1)),最后遍历[1, n]各下标,如果该下标对应的元素值大于0则说明缺失的数为该下标值,如果下标为0则说明n缺失,如果没有缺失则答案为n+1

代码如下:

发表评论

电子邮件地址不会被公开。