Closed congr closed 5 years ago
class Solution {
// 0 1 2 3
// 1 2 3 4
public int firstMissingPositive(int[] nums) {
int N = nums.length;
for (int i = 0; i < nums.length; ) {
if (nums[i] == i+1) i++; // nums = {1 2 3 4}
else {
int ind = nums[i]-1;
if (ind >= 0 && ind < N && nums[ind] != nums[i]) swap (nums, ind, i);
else i++;
}
System.out.println("i:" + i + " " + Arrays.toString(nums));
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i+1) return i+1;
}
return nums.length+1; // !!!
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Your input
[1,2,0]
Your stdout
i:1 [1, 2, 0]
i:2 [1, 2, 0]
i:3 [1, 2, 0]
Your answer
3
Expected answer
3
Your input
[3,4,-1,1]
Your stdout
i:0 [-1, 4, 3, 1]
i:1 [-1, 4, 3, 1]
i:1 [-1, 1, 3, 4]
i:1 [1, -1, 3, 4]
i:2 [1, -1, 3, 4]
i:3 [1, -1, 3, 4]
i:4 [1, -1, 3, 4]
Your answer
2
Expected answer
2
https://leetcode.com/problems/first-missing-positive/description/