Easy JAVA solution with solving idea


  • 0
    M

    Go through array and put positive number n into nums[n-1]. Code looks it's O(n^2), however every positive number will be put only once, time is limited within O(n).

    Enjoy!

    public class Solution {
    
        public int firstMissingPositive(int[] nums) {
    	
    	int length = nums.length, cur, next;
    	
    	for(int i = 0; i<length; i++) {
    		if((cur = nums[i])>0) {
    			while(cur>0 && cur<=length) {
    				next = nums[cur-1];
    				nums[cur-1] = cur;
    				if(next==cur) cur = 0;
    				else cur = next;
    			}
    		}
    	}
    	
    	for(cur = 0; cur<length && cur+1==nums[cur]; cur++);
    	return cur+1;
        
        }
    }

Log in to reply
 

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