缺失的数字
给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
思路
不会,学习一下
将数组视为哈希表
- 将负数设为数组长度 + 1
- 将正数对应的索引设置设为负数。如果有两个相同的正数,那么对应索引位置会是正数
- 遍历数组,返回第一个正数的下标 + 1
解答
class Solution {
public int firstMissingPositive(int[] nums) {
int length = nums.length;
for (int i = 0; i < length; i++) {
if (nums[i] <= 0) nums[i] = length + 1;
}
for (int i = 0; i < length; i++) {
int num = Math.abs(nums[i]);
if (num <= length) nums[num - 1] = -Math.abs(nums[num - 1]);
}
for (int i = 0; i < length; i++) {
if (nums[i] > 0) return i + 1;
}
return length + 1;
}
}