A hashmap based solution, but in-place


  • 7
    Y

    A[] is an array, but we can also treat it as an hashmap,
    If A[i] > 0, it mean i+1 exist,
    If A[i] < 0, it mean i + 1 does not.
    Here is the code

    class Solution {
    public:
        int firstMissingPositive(int A[], int n) {
            /* first iteration: change all the value out of bound to (n + 1) */
        	const int out_of_bound = n + 1;
        	for (int i = 0; i < n; ++i)
        		if (A[i] <= 0)
        			A[i] = out_of_bound;
    
    		/* second iteration: construct a hash map. map<int, int>, first argument is index
    		 * second argument: if positive, it exist, else, it doesn't. e.g. A[0] = 4,
    		 * A[0] (i.e. 1) exist */
    	 	for (int i = 0; i < n; ++i) {
    	 		int abs_i = abs(A[i]);
    	 		if (abs_i <= n)
    	 			A[abs_i-1] = -abs(A[abs_i-1]);
    	 	}
    
    	 	/* third iteration: check the first positive value in A[] */
    	 	for (int i = 0; i < n; ++i) {
    	 		if (A[i] > 0)
    	 			return i + 1; 
    	 	}
    	 	return n + 1;
        }
    };

  • 2
    H

    I think in your code A[i] < 0 means i + 1 exist.


  • 0
    G

    Thx for sharing, I think I've learned a new skill from your code. :)


Log in to reply
 

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