1. Runtime Distribution

2. Submission Details

3. Description

Given an unsorted integer array, find the first missing positive integer.
Your algorithm should run in O(n) time and uses constant space.

4. Example

Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

5. Explanation

The key here is to use swapping to keep constant space and also make use of the length of the array, which means there can be at most n positive integers. So each time we encounter an valid integer, find its correct position and swap. Otherwise we continue.

6. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

int firstMissingPositive(int * nums, int numsSize)
{
	for(int i = 0; i< numsSize; i++)
	{
		if(nums[i] > 0 && nums[i] <= numsSize && nums[i] != i + 1)
		{
			if(nums[i] != nums[nums[i] - 1])
			{
				int tmp = nums[nums[i] - 1];
				nums[nums[i] - 1] = nums[i];
				nums[i--] = tmp;
			}
		}
	}

	int i = 0;
	for (; i < numsSize && nums[i] == i + 1; i++);
	return i + 1;
}

[/restab]
[/restabs]

7.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

#include

int firstMissingPositive(int * nums, int numsSize)
{
	for(int i = 0; i< numsSize; i++)
	{
		if(nums[i] > 0 && nums[i] <= numsSize && nums[i] != i + 1)
		{
			if(nums[i] != nums[nums[i] - 1])
			{
				int tmp = nums[nums[i] - 1];
				nums[nums[i] - 1] = nums[i];
				nums[i--] = tmp;
			}
		}
	}

	int i = 0;
	for (; i < numsSize && nums[i] == i + 1; i++);
	return i + 1;
}

int main()
{
	int nums[] = { 3, 4, -1, 1 };
	printf("%d\n", firstMissingPositive(nums, 4));
	system("pause");
	return 0;
}

[/restab]
[/restabs]