1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int firstMissingPositive(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] >= 1 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
int targetIdx = nums[i] - 1;
swap(nums, i, targetIdx);
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 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;
}
}
|
cyclic sort.
疯狂位置交换法. 就是把每个元素放到它们该去的位置. 比如1要到index 0, 2要到index 1以此类推. 我们放好一个数字后, 交换回来的数字它该去的位置可能也不是现在的位置, 于是我们也要把它放到它该去的位置. 那么什么时候停止呢? 当我们发现我们要放的数字它应该去的位置上放着的是和我们一样的数字, 也就是我们要去的位置上, 已经有一个数字在这里, 而且这个数字的正确位置也是这里, 到这时我们就停止. 因为这意味着这个数字该去的位置上已经有了正确的数字. 我们现在有的这个数字就先待在这里了. 我们的目标是尽可能多的让每个位置都装着它该装的数字. 这个目的我们目前已经达到, 需要走入下一个元素来继续这个交换过程.
时间复杂度: O(n) 因为每个数字会去它该去的位置, 这是O(1)的操作. 出界的数字不考虑, 已经是正确位置的也不考虑这些判断也都是O(1)的操作. 我们遍历所有的元素, 因此是O(n).
空间复杂度: O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int firstMissingPositive(int[] nums) {
boolean containsOne = false;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
containsOne = true;
} else if (nums[i] <= 0 || nums[i] > nums.length) {
nums[i] = 1;
}
}
if (!containsOne) {
return 1;
}
for (int i = 0; i < nums.length; i++) {
int targetIdx = Math.abs(nums[i]) - 1;
nums[targetIdx] = -Math.abs(nums[targetIdx]);
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return nums.length + 1;
}
}
|
第二种解法. array index标记法. nums的length是n的话, 那么能装从1到nums.length的范围内的positive. 两端都是inclusive的. 我们首先把超出这个范围的数字剔除掉, 然后把剩下的数字在它们应该在的位置上标记上负号. 如何剔除? 一开始我想着是把超出范围的数字都赋成0, 但是这有个问题就是这个位置无法标记, 因为0的负数还是0. 因此我们必须把剔除的数字标记成正数. 这里我们选择了1. 但这有个前提就是, 1必须存在. 因此我们第一次遍历不仅看有没有1还要剔除出界的数字. 然后第二遍就把在界内的数字对应的位置标记为负数. 第三遍遍历就看到哪个位置时不为负, 此时这个位置应该待的数字就是first missing positive. 如果全都是负, 那说明1到nums.length都在了, 于是返回nums.length + 1.
时间复杂度: O(n)
空间复杂度: O(1)
