给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
目录
思路一：利用负数进行区分
分析：
思路二：交换法
分析：
总结：
思路一：利用负数进行区分
int firstMissingPositive(int* nums, int numsSize) {
for (int i = 0; i < numsSize; ++i) {
if (nums[i] <= 0) {
nums[i] = numsSize + 1;
}
}
for (int i = 0; i < numsSize; ++i) {
int num = abs(nums[i]);
if (num <= numsSize&&num>0) {
nums[num - 1] = -abs(nums[num - 1]);
}
}
for (int i = 0; i < numsSize; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
return numsSize + 1;
}时间复杂度O(n)，空间复杂度O(1）
分析：
本题一开始想到首先负数肯定要排除，又因为若数组内数为1到numsSize，则输出numsSize加一，所以将负数赋值为numsSize加一。而后想到可以将对应下标的数变为负数，之后将数组遍历一遍输出数组在该下标为正数的下标即可
思路二：交换法
int firstMissingPositive(int* nums, int numsSize) {
for (int i = 0; i < numsSize; ++i) {
while (nums[i] > 0 && nums[i] <= numsSize &&
nums[nums[i] - 1] != nums[i]) {
int t = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i], nums[i] = t;
}
}
for (int i = 0; i < numsSize; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return numsSize + 1;
}时间复杂度O(n)，空间复杂度O(1）
分析：
第二种思路是将数组每个数交换到正确的位置上再遍历输出该位置存在不等于下标最小数。编写的过程中需注意若交换的两个数相等则可能出现死循环的情况，判断条件要加上nums[nums[i] - 1] != nums[i]。文章来源：https://www.toymoban.com/news/detail-604529.html
总结：
两个方法比较而言，利用负数进行区分的方法更加快速，只需遍历三次原数组即可，而交换法在交换的过程中每个i可能会进行多次交换；在代码长度上，交换法代码长度较短，更加简洁。文章来源地址https://www.toymoban.com/news/detail-604529.html
到了这里，关于leetcode做题笔记41的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
