leetcode 41 | 缺失的第一个正数 解题思路和方法
注：本文整理自cnblog
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3示例 2:
输入: [3,4,-1,1]
输出: 2示例 3:
输入: [7,8,9,11,12]
输出: 1说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
思路：这个题刚開始是没有思路的，难就难在O(n)时间内常数量空间，所以此题较为考察思维敏捷性。其解题核心思想是将数组的第i位存正数i+1。最后再遍历一次就可以。
其它人的思想，我也是看了这个思想自己写的代码。
尽管不能再另外开辟很数级的额外空间，可是能够在输入数组上就地进行swap操作。
思路：交换数组元素。使得数组中第i位存放数值(i+1)。
最后遍历数组，寻找第一个不符合此要求的元素，返回其下标。整个过程须要遍历两次数组，复杂度为O(n)。
下图以题目中给出的第二个样例为例，解说操作过程。
首先思路上，其次临界条件，这题和以下题异曲同工：
n个元素的数组，里面的数都是0~n-1范围内的，求数组中反复的某一个元素。没有返回-1, 要求时间性能O(n) 空间性能O(1)。
代码还是比較简单。例如以下：
static inline void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
static int firstMissingPositive(int* nums, int numsSize)
{
if (numsSize < 1) {
return 1;
}
int i = 0;
//2 1 3 4
while (i < numsSize) {
//x大于0，x不等于当前位置索引，x小于数组大小，x不等于n[x]的值
if (nums[i] != i + 1 && nums[i] > 0 && nums[i] <= numsSize && nums[i] != nums[nums[i] - 1]) {
//交换x和n[x]
swap(nums + i, nums + nums[i] - 1);
} else {
i++;
}
}
//寻找第一个空位
for (i = 0; i < numsSize; i++) {
if (nums[i] != i + 1) break;
}
return i + 1;
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-02-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
