My 0ms C++ recursive Solution


  • 0
    B

    This solution is similar with makuiyu's solution but go through the vector in a reverse order.m is to record the newest position that has the wrong number. So that we dont need to go through the vector twice.

    	int firstMissingPositive(vector<int>& nums) {
    		int m = nums.size();
    
    		for (size_t i = nums.size(); i != 0; --i){
    			if (!traceFinder(nums, i - 1, m))
    				m = i - 1;
    		}
    		return m + 1;
    	}
    	bool traceFinder(vector<int>& nums, size_t n, size_t m){
    		if (nums[n] > m || nums[n] < 1)
    			return false;
    		else if (nums[n] == n + 1)
    			return true;
    		else if (nums[nums[n] - 1] == nums[n])
    			return false;
    		else{
    			swap(nums[n], nums[nums[n] - 1]);
    			return traceFinder(nums, n, m);
    		}
    	}
    

    Because it is a recursive way, O(n) space is needed. You can rewrite it in a non-recursive way like this which is a little bit slower.

    int firstMissingPositive(vector<int>& nums) {
    		int m = nums.size();
    
    		for (size_t i = nums.size(); i != 0; --i){
    			while (nums[i-1] <= m && nums[i-1] >= 1 && nums[i-1] != i && nums[nums[i-1] - 1] != nums[i-1])
    		        swap(nums[i-1], nums[nums[i-1] - 1]);
            	if (nums[i-1] != i)
            		m=i-1;
    		}
    		return m + 1;
    	}
    

Log in to reply
 

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