题解 | #数组中未出现的最小正整数#

数组中未出现的最小正整数

题目：

给定一个无序整型数组arr，找到数组中未出现的最小正整数。

要求时间复杂度为O(N)空间复杂度为O(1)。

例如：

arr=[-1,2,3,4]。返回1。

arr=[1,2,3,4]。返回5。

找到自然数从1-n中，第一个没有出现在给定数组中的

题解一（空间复杂度O（n））：

我们知道数组的长度为n，最后的结果一定在1-n+1之间。我们创建一个长度为n的数组pos，元素初始化为0，之后遍历给定的数组，数组如果有数字i出现，就置pos[i-1]=1。最后遍历一遍pos，发现有pos[i]=0的话，那么最后结果就为i+1。如果在遍历过程中没有返回结果，那么返回n+1。

举个例子有数组arr = [-1, 2, 3, 4]，生成的pos为[0,1,1,1]。遍历发现pos[0]=0，那么返回0+1

int minNumberdisappered(vector<int> &arr) {
    int n = arr.size();
    vector<int> pos(n, 0);
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) {
            pos[arr[i] - 1] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (pos[i] == 0) {
            return i + 1;
        }
    }
    return n + 1;
}

时间复杂度： $O(n)$ ，我们对两个数组分别遍历了一遍，数组长度均为n。

空间复杂度： $O(n)$ ，我们创建了长度为n的pos数组。

题解二：缩减空间复杂度

题解一开辟了新的pos数组存储了出现过的数组，如果我们直接在原数组上修改位置，就不用开辟新的数组了。

值为i的数应该存放在arr[i-1]的位置，如果我们尽可能的把所有数放到指定的位置，最后剩下的数就是我们要求的结果。

我们用l表示在1-l的正整数有合适的位置，初始化为0，用r表示右边界，在这个边界的右边都是没有正确位置的数。r的初值为N，所有的数都有位置（不一定是正确的位置）。

当[l+1-r]之间的数，如果其数据不合法，指超越了l+1-r这个范围，我们直接令该数据等于arr[r-1],同时r左移一位如果其数据合法，但其所在位置不对，那么就需要交换到正确的位置arr[l]应该在arr[l]-1处，所有将arr[arr[l]-1]与arr[l]交换即可。

举个例子：如数组arr[-1,2,3,4]

图片说明

代码实现如下：

int minNumberdisappered(vector<int>&arr)
{
    int l = 0;
    int r = arr.size();
    while(l < r)
    {
        //元素arr[l]在位置l=arr[l]-1处
        if(arr[l] == l + 1){
            l++;
        }
        else if(arr[l] > r || arr[l] <= l || arr[arr[l] - 1] == arr[l])//不合法的数据
        {
            arr[l] = arr[--r];
        }
        //arr[l]处的数合法但是没有在理想的位置上
        else
        {
            swap(arr[l], arr[arr[l] - 1]);
        }
    }
    return l + 1;
}

时间复杂度： $O(n)$ ，对数组进行了一遍遍历求和

空间复杂度： $O(1)$ ，没有额外申请数组。

题解三（可ac但并不完全正确）：

数组中只有一个数不符合要求。如果我们把所有符合要求的数(1到n之间的数)相加和为total，与 $\frac{n(n+1)}{2}$ 相减，若差值为0，则返回n+1，不为0则返回差值。

这种代码在nc上是ac的，nc测试用例不足。

如当所有的数都在1-n之间，如[1,2,2,3,5],，total值为13， $\frac{n(n+1)}{2}-total>0$ ，差值为2，但要求的结果为4.

int minNumberdisappered(vector<int> &arr) {
      int n = arr.size();
    int total = 0;
    int sum = n*(n+1)/2;
    int c = total-sum;
    for(int i=0;i<n;i++){
        if(arr[i]<=0||arr[i]>n){
            continue;
        }
        else{
            //将1-n之间的数相加
            total+=arr[i];
        }
    }
    return total-sum==0?n+1:sum-total;
}

时间复杂度： $O(n)$ ，对数组进行了一遍遍历求和

空间复杂度： $O(1)$ ，没有额外申请数组。