给定一个未排序的整数数组，找到最小的缺失正整数。

找到具有恒定额外空间的O（n）顺序元素。

范例1：

输入： [ 2, 3, -1, -2]

Output: 1

范例2：

输入： [5, 6, 7, 8, 9]

Output: 1

解决方案说明：

解决方案实际上非常简单。而且我们知道整数从1到n开头而不是零。

因此，我们要做的是，首先计算数组中元素的数量，然后在其中填充给定的数量’的索引。假设我们有一个包含“ n”个元素的数组。

我们按照以下步骤获取结果：

第1步：

   Iterate throughout the array
   Set current_value = arr[i]
      If current_value < 0 and current_value > array_length
         Ignore and continue
      Else
         Set current_value to the index, whose value is equal to current_value

第2步：

                  Once completed step 1, iterate throughout the array to find which smallest index is not having value. You will get your missing element.

例：

输入：

[2, 3, -1, -2]

Pass 1:
   Current_value = 2
   2 > 0 && 2 > 4 true
   swap 2 and -1

   resulting array:
   [-1, 3, 2, -2]

Pass 2:
   Current_value = 3
   3> 0 && 3 > 4 true
   swap 3 and -2
  
   resulting array:
   [-1, -2, 2, 3]

Pass 3:
   Current_value = 2
   2> 0 && 2 > 4 true
   as 2 is in already at it’s index, leave it.
   
   resulting array:
   [-1, -2, 2, 3]

Pass 4:
   Current_value = 3
   3> 0 && 3 > 4 true
   as 3 is in already at it’s index, leave it.
   
   resulting array:
   [-1, -2, 2, 3]

最后遍历整个数组：

We find out that the first index i.e arr[1] != 1. Hence the lowest missing element is 1.

这里的时间复杂度是O（n），因为我们使用while [仅在这里进行数字重新排列]并访问了最后一次通过for进行访问，从而将每个元素放置在正确的位置。因此，O（n）。

C语言解决方案：

#include<stdio.h>

int firstMissingPositive(int arr[], int length) {
	int n = length;
	int itr = 0;
	for ( itr = 0; itr < n; itr++) {

		while (arr[itr] != itr) {
			// we shall swap for 上 ly +ve integers and is less than the length of the array
			if (arr[itr] <= 0 || arr[itr] >= n)
				break;
 
			//handle duplicate elements
			if(arr[itr] == arr[ arr [ itr ] ] )
			{
                break;
            }

			// swap elements
			int temp = arr[itr];
			arr[itr] = arr[temp];
			arr[temp] = temp;
		}
	}
 
 // start the "itr" value from 0, if you want to consider 0 as smallest +ve integer.
	for (int itr = 1; itr < n; itr++) {
		if (arr[itr] != itr)
			return itr;
	}
	return n;
}


int main()
{
	int arr [100] = {2,1,4,5,6};
	int length = 5;
	int firstMissingPositiveInteger = 0;

	firstMissingPositiveInteger = firstMissingPositive(arr, length);

	printf("The smallest missing positive integer is = %d\n", firstMissingPositiveInteger );

}

输出：

The smallest missing positive integer is = 3

该网站上可用的教程列表：