LeetCode 41 - First Missing Positive

作者 QIFAN 日期 2017-02-24
LeetCode 41 - First Missing Positive

原题链接: 41. First Missing Positive


题干

给定一个无序数组,找到缺失的第一个正整数。这道题有点模糊,正整数的范围是 1 ~ n 也就是说,找到数组中缺失的第一个。

要求时间复杂度 $O(N)$ ,空间复杂度 $O(1) $

思路

这个也是没看清楚题意(或者说我觉得自己已经理解了),就开始思考了。真正遇到问题还是应该先确认。如果我能够先进行几个 test case ,就不会陷入一脸懵逼的境地了。

输入 [5,6,8] 返回 1
输入 [-3,-2,0] 返回 1

也就是说,一个长度为 n 的数组,很完美的位置就是 1 放第一个,2 放第二个,以此类推。如果哪个位置没有应该需要的数字,那个数字就是缺失的。假设有一个数为 num ,若它是一个正整数且小于 n ,那它在这个数组里就有自己的位置,也就是 array[num - 1] 应该等于 num 。将这两个位置调换,并对调换过来的数进行同样的操作。如果 num < 0 或者 num > array.length ,那这个数组里没有 num 的位置,可以直接往后。

有一个 trick 的地方在,如果原位置与调换的位置的值是一样的或要调换位子的值已经合理了,那也要直接往后,不然就死循环了。

在遍历一遍后,如果有位置上的值并不是合理的值,那这个位置所对的正整数是缺失的,如果数组中的数合理,那第一个缺失的就是 n 。

代码:

public int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0) {
return 1;
}
int i = 0;
int length = nums.length;
while (i < length) {
if ((!inRange(nums[i], length)) || (inRange(nums[i], length) && (isValid(nums[nums[i] - 1], nums[i] - 1) || nums[nums[i] - 1] == nums[i]))) {
i++;
} else {
swap(nums, i, nums[i] - 1);
}
}
i = 0;
while (i < length && i == nums[i] - 1) {
i++;
}
return i + 1;
}
private boolean inRange(int num, int length) {
return num > 0 && num <= length;
}
private boolean isValid(int num, int i) {
return num == i + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}