C++ solution, no extra memory, using "pseudo sort"


  • 5
    D

    The answer is between 1 and n, where n is the size of the vector and the trick is that you have to "pseudo sort", what I mean with that? Well, if the number nums[i] is between 1 and n you have to put it in the correct position swapping it with the number nums[nums[i]] if they are different.
    For example: [1,2,0] ->[1,2,0];
    [3,4,-1,1] ->[1,-1,3,4];
    [0,10,1,3,6,4]->[1,10,3,4,0,6].
    You can do this in O(n), than it's easy to find the solution

    int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    int p = 0;
    int expected = 1;
    
    //pseudo sort
    while (p < n) {
    	int pPos;
    	int aux;
    	
    	if (nums[p] > 0 && nums[p] <= n) {
    		pPos = nums[p] - 1;
    		if (nums[pPos] != nums[p]) {
    			aux = nums[p];
    			nums[p] = nums[pPos];
    			nums[pPos] = aux;
    			p--;
    		}
    	}
    
    	p++;
    }
    
    //Finding the answer
    for (size_t i = 0; i < n && nums[i] == expected; i++, expected++);
    
    return expected;
    

    }


  • 0
    L

    But what if some positive element appears more than once? Eg. -1,1,2,3,4,3,3,6,4


Log in to reply
 

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