My java solution


  • 1
    T

    as discussed elsewhere, the idea is still basically sorting, but instead of regular sorting, we kind of have radix sort here. but the value range is so big (-infinity to max) that regular radix sorting doesn't work. but the goal of the problem is not to solve everything, we just need to sort 1---A.length, if A does contain the full range. all the rest would be discarded. this would mean to sort the possible appearances of elements of A into the 1--N buckets. anything not appearing from this range would be missing.

    then stated more clearly the problem becomes trying to move the N elements back to their 'original' locations, with the constraint that you can't have extra storage.

    public class Solution {
    public int firstMissingPositive(int[] A) {
        int tmp;
        for(int i=0;i<A.length;i++) {
            // chase the chain
            int ptr = A[i]-1;
            while (ptr >=0 && ptr < A.length && A[ptr] != ptr +1) {
                tmp = A[ptr]-1;
                A[ptr] = ptr+1;
                ptr = tmp;
            }
        }
        for(int i=0;i<A.length;i++) {
            if (A[i] != i+1)
                return i+1;
        }
        
        return A.length+1;
    }
    

    }


Log in to reply
 

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