Java Accepted - no swap, just use "push"


  • 9
    D

    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;
        }
    }

  • 0
    B

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


  • 0
    D

    which line will overflow?


  • 0
    G

    Is this run in O(n)?


  • 0
    G

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


  • 0
    B

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


Log in to reply
 

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