给定一个整数数组，找到线性时间和常量空间中第一个缺失的正整数

换句话说，找到数组中不存在的最小正整数。该数组也可以包含重复项和负数。 这个问题是 Stripe 在编程采访中提出的。我设计了一个解决方案，如下所示：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int arr[]={1,-1,-5,-3,3,4,2,8};
    int size= sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr+size);
    int min=1;

    for(int i=0; i<size; i++){
        if(arr[i]>min) break;
        if(arr[i]==min) min=min+1;
    }
    cout<<min;
    return 0;
}

这里，我先对数组进行排序，然后遍历数组一次。在遍历数组之前，我将一个名为“min”的变量初始化为1。现在，在遍历数组时，当我们得到一个等于min的整数时，我们只需增加min的值即可。这确保了 min 变量保存尚未发生的最新最小正整数。 你能想到更好的方法吗？提前致谢。

假设数组可以修改，

1. 我们将数组分为两部分，第一部分仅包含正数。假设我们的起始索引为0和结束索引为end（独家的）。

2. 我们从索引开始遍历数组0 to end。我们取该索引处元素的绝对值 - 假设该值为x.

   1. If x > end我们什么也不做。
   2. 如果不是，我们对索引处的元素做符号x-1消极的。 (澄清：我们不切换标志。如果值为正，则变为负。如果为负数，则仍为负数。在伪代码中，这将类似于if (arr[x-1] > 0) arr[x-1] = -arr[x-1]并不是arr[x-1] = -arr[x-1].)

3. 最后，我们从索引再次遍历数组0 to end。如果我们在某个索引处遇到正元素，我们输出index + 1。这就是答案。但是，如果我们没有遇到任何正元素，则意味着整数1 to end出现在数组中。我们输出end + 1.

也有可能所有数字都是非正数end = 0。输出end + 1 = 1仍然正确。

所有步骤都可以在O(n)时间和使用O(1) space.

Example:

Initial Array:            1 -1 -5 -3 3 4 2 8
Step 1 partition:         1 8 2 4 3 | -3 -5 -1, end = 5

在步骤 2 中，我们更改正数的符号以跟踪哪些整数已经出现。例如，这里array[2] = -2 < 0，这表明2 + 1 = 3数组中已经发生了。基本上，我们改变具有索引的元素的值i为负数，如果i+1是在数组中。

Step 2 Array changes to: -1 -8 -2 -4 3 | -3 -5 -1

在步骤 3 中，如果某个值array[index]是正数，这意味着我们没有找到任何整数值index + 1在步骤 2 中。

Step 3: Traversing from index 0 to end, we find array[4] = 3 > 0
        The answer is 4 + 1 = 5