C++在未排序的数组中找到第一个缺失的正值

Question

我正在努力理解 this在未排序的数组中找到第一个缺失的正值的解决方案。它是这样工作的

1, locate min and max of the input, and mark the negative values with a special positive value. 2. After ensure the min starts with 1 (otherwise we know ‘1’ is missing), we scan the input, similar to counting sort, since we can’t use extra space. I can’t mark the values to negative to indicate the slot is taken.

3.scan the range the input where we just did count on between valMin and valMax, if we can any slot isn’t taken (as in is positive) then we know that’s the slot where the missing number is.

我的问题是这两条线在做什么？

int &val = nums[abs(num) - valMin];
if (val > 0) val = -val;

例如，如果您的输入数组是 { 1, -3, 2, 1, 4, 3 }; 在这一点之后，您的数组变为 -1,-2147483647,-2,-1,4,3

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>

using namespace std;

int firstMissingPositive(vector<int> &A) {

        int valMin = INT32_MAX, valMax = 0;

        for (auto &num:A) {

            if (num > 0) {
                valMin = min(valMin, num);
                valMax = max(valMax, num);

            } else {

                num = INT32_MAX;

            }
        }

        for (auto &num:A)
            cout << num << ",";

        cout << "\n";

        if (valMin != 1) return 1;
        for (int &num:A) {
            if (num != 0 and abs(num) != INT32_MAX) {
                int &val = A[abs(num) - valMin];
                if (val > 0) val = -val;
            }
        }
        for (auto &num:A)
                    cout << num << ",";

        //scan the range the input where we just did count on between valMin and valMax,
        //if we can any slot isn’t taken (as in is positive) then we know that’s the slot where the missing number is.

        for (int i = valMin; i < valMax; ++i) {
            if (A[i - valMin] > 0) return i;
        }
        return valMax + 1;
    }

int main()
{
    std::vector<int> v = { 1, -3, 2, 1, 4, 3 };
    int answer = firstMissingPositive(v);
    cout << answer;
    return 0;
}

Answer 1

在这里，

since we can’t use extra space. I *can mark the values to negative to indicate the slot is taken.

解决方案是使用相同的输入数组 来标记所占用的插槽。

这些行:

int &val = nums[abs(num) - valMin]; 如果 (val > 0) val = -val;

abs(num)，因为可能存在像{0,-4,-5,6,1,2,3}这样的情况，所以'2'会被标记为'-2 ' 在迭代之前。

这些行是，

1. 获取索引“num”处的值 - 1，本质上，因为 valMin 将始终为 1，否则它会返回该函数。

2. 然后检查这个值是否为正，这意味着这个索引以前从未被逻辑检查过，否则它就是负数。因此，如果值为正，make 为负，以标记对应于该索引的值存在于数组中。

因此，例如，在输入数组中，迭代将是这样的:

{0,-4,-5,6,1,2,3} => {0,MAX,MAX,6,1,2,3}
{0,MAX,MAX,6,1,2,3} => {0,MAX,MAX,6,1,-2,3}
{0,MAX,MAX,6,1,2,3} => {0,MAX,MAX,6,1,-2,3}
{0,MAX,MAX,6,1,2,3} => {0,-MAX,MAX,6,1,-2,3}
{0,MAX,MAX,6,1,2,3} => {0,-MAX,-MAX,6,1,-2,3}

然后，if (A[i - valMin] > 0) return i; 将检查第一个为正的条目，即 i-valMin 或者我应该说i-1。因此，从本质上讲，第一个正数 index + 1 就是答案。

此处，在示例输入数组中，{0,-MAX,-MAX,6,1,-2,3}；第一个正指数是 3，所以答案是 3+1 即 4