Solution in C++


  • 0
    P
    class SolutionB 
    {
    public:
    	int firstMissingPositive(vector<int>& nums) 
    	{
    		int len = nums.size(), j = 1;
    		// analysis the below for statement time complexity
    		// just need to count how many time the judgement statement in while has to 
    		// be done.
    		// if has k positive elements in nums(n elements), only need to do swap statement k time
    		// after that we just need to do while statement one time at a specified i.
    		// So time complexity is O(k + n - 1) == O(2n) == O(n)
    		for (int i = 0; i < len; ++i)
    		{
    			while (nums[i] > 0 && nums[i] < len + 1 && nums[nums[i] - 1] != nums[i])
    				std::swap(nums[nums[i] - 1], nums[i]);
    		}
    		while (j - 1 < len && nums[j - 1] == j) ++j;
    		return j;
    	}
    };

Log in to reply
 

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