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

Question

换句话说，找到数组中不存在的最低正整数。该数组也可以包含重复项和负数。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变量保存尚未出现的最新的最小正整数。您能想到更好的方法吗？提前致谢。

Answer 1

假设可以修改数组，

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

2. 我们遍历数组的索引0到end。我们在该索引处获取元素的绝对值-假设该值为x。

   1. 如果x > end我们什么都不做。
   2. 如果不是，则使索引处元素的符号为x-1负。

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

所有数字都是非正整数也可能是这种情况end = 0。输出end + 1 = 1保持正确。

所有步骤都可以O(n)及时且O(1)节省空间地完成。

例：

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

Answer 2

这实际上是一个要求时间和空间的 LeetCode 问题，因此对输入进行排序或将其转换为集合是行不通的。这是一个在时间上运行并使用空间的 Python 3 实现。基本上，我们尝试将每个元素放入.O(n)O(1)O(n)O(1)inums[i - 1]

def missing_int(self, nums: List[int]) -> int:
    i = 0
    n = len(nums)

    while i < n:
        j = nums[i]
        if 0 < j < n and j != nums[j - 1]:
            nums[i], nums[j - 1] = nums[j - 1], nums[i]
        else:
            i += 1

    return next((x + 1 for x in range(n) if nums[x] != x + 1), n + 1)

测试：

def test_missing_int(self):
    assert func.missing_int([1, 2, 1, 0]) == 3
    assert func.missing_int([3, 4, -1, 1]) == 2
    assert func.missing_int([7, 8, 9, 11, 12]) == 1
    assert func.missing_int([1]) == 2
    assert func.missing_int([]) == 1
    assert func.missing_int([0]) == 1
    assert func.missing_int([2, 1]) == 3
    assert func.missing_int([-1, -2, -3]) == 1
    assert func.missing_int([1, 1]) == 2
    assert func.missing_int([1000, -1]) == 1
    assert func.missing_int([-10, -3, -100, -1000, -239, 1]) == 2
    assert func.missing_int([1, 1]) == 2