给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-missing-positive
解题思路
先遍历数组, 试图将元素1放在位置0, 元素2放在位置1, ...以此类推
忽略负数和超过数组长度的数
调整完数组后, 遍历数组, 找出第一个不符合"元素值 = 索引 + 1"的即为答案
如果全都满足则直接返回数组长度 + 1
nums[i] != nums[nums[i] - 1] 判断某元素是否在该元素 - 1对应的位置
也就是元素 1 是否在位置 0, 元素 2 是否在位置 1
代码
class Solution {
public int firstMissingPositive(int[] nums) {
// 遍历数组
for (int i = 0; i < nums.length; i++) {
// 试图将元素1放在位置0, 元素2放在位置1, ...以此类推
// 忽略负数和超过数组长度的数
while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
// 调整完数组后, 遍历数组, 找出第一个不符合"元素值 = 索引 + 1"的即为答案
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 如果全都满足则直接返回数组长度 + 1
return nums.length + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
