Java Solution with iteration and in-place


  • 1
    A

    Goal: each positive integer p should be placed at index p-1; in the end, iterate from index=0 to right, stop at the first index whose value is non-positive; and return the missing integer as index+1.

    To achieve this:

    1. Iterate through the array.
    2. If current element, 'curr', is positive and its value is not equal to index+1, move it to index+1.
    3. If there is another positive integer at index+1, continue moving that integer.
    4. After moving curr to the right location, reset this index to 0.
    5. In the end, iterate from index 0 to right, stop at first index with non-positive value. return index+1.
        public int firstMissingPositive(int[] A) {
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0 && A[i] != i+1) {
                int curr = A[i];
                A[i] = 0;
                while (curr > 0 && curr-1 < A.length) {
                    int next = A[curr-1];
                    A[curr-1] = curr;
                    if (curr != next)   // have to check this, otherwise infinity loop
                        curr = next;    // continue placing next at right index, if it's positive.
                    else
                        curr = 0;
                }
            }
        }
        // look for first index with non-positive value
        for (int i = 0; i < A.length; i++) {
            if (A[i] <= 0)
                return i+1;
        }
        return A.length + 1;
    }

  • 1
    M

    Your code is too complex. Loo at my code below:

    public int firstMissingPositive(int[] A) {
        if (A == null || A.length == 0) {
            return 1;
        }
        
        // Put the corresponding positive value in the index that equals to its value
        int len = A.length;
        for (int i = 0; i < len;) {
            int num = A[i];
            if (num > 0 && num < len && num != i && num != A[num]) {
                A[i] = A[num];
                A[num] = num;
            } else {
                ++i;
            }
        }
        
        // Scan the array to find the first value that is not equal to its index, then it is the missing value
        // Test small examples first
        int missingValue = A[0] == len ? len+1 : len;
        for (int i = 1; i < len; ++i) {
            if (A[i] != i) {
                missingValue = i;
                break;
            }
        }
        
        return missingValue;
    }

  • 0
    J

    if (num > 0 && num < len && num != i && num != A[num]) can be
    if (num > 0 && num < len && num != A[num])


Log in to reply
 

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