Java Accepted - no swap, just use "push"

• number i should be in index i-1 of nums.
keep pushing number A into its right place, and push out the existing number B from this place and continue push number B into its right place again.

i.e. start from the first number 3

Index:0, 1, 2, 3, 4

Array: 3, 4, 5, 1, -1 curr number 3

Array: 3, 4, 3, 1, -1 push 3 to index 2, the number being pushed out is 5

Array: 3, 4, 3, 1, 5 push 5 to index 4, the number being pushed out is -1, so we stop.

Array: 3, 4, 3, 4, 5 next number is 4, push 4 to index 3, the number being pushed out is 1

Array: 1, 4, 3, 4, 5 push 1 to index 0, the number being pushed out is 3

Array: 1, 4, 3, 4, 5 since 3 is already at index 2 (right place), we stop

check next number is 3 (already right place), then 4 (right place), then 5 (right place), stop.

Now we compare each number with its index, should be number == index+1, otherwise the number is the first missing positive.

``````public class Solution {
public int firstMissingPositive(int[] nums) {
// nums[i] -> i+1
int next;
for (int i = 0 ; i < nums.length; i++) {
int curr = nums[i];
if (curr > 0 && curr != i+1 && curr <= nums.length) {
do {
next = nums[curr-1];
nums[curr-1] = curr;
curr = next;
} while (curr > 0 && curr <= nums.length && nums[curr-1] != curr);
}
}
int j;
for (j = 0; j < nums.length; j++) {
if (nums[j] != j+1)
break;
}
return j+1;
}
}``````

• What if the size of the int[] nums is smaller than the number?
For example: {233, 1, 2, 3}
nums[233] will overflow.

• which line will overflow?

• Is this run in O(n)?

• nums[curr-1],when curr is much larger than the size of the array---next = nums[curr-1]; curr = next;

• Ahhhh, got it. We only cares about those elements which are within the length.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.