使用 O(n) 运行时查找范围内的元素

我正在尝试编写一个函数，从用户接收一个大小为“N”的数组，其值在0--->N-1之间，如果所有值在0---->N之间，该函数应该返回“1” -1 是否存在，否则返回 0。我们可以假设用户输入的数字只是有效值。 0---->N-1之间。

示例：N=5，值：2,1,4,0​​,3---->返回 1， N=5，值：2,3,4,0,3---->返回0

我尝试了各种方法来解决这个问题。

考虑过阶乘，但发现有很多方法可以使用重复的数字和唯一的数字来获得相同的阶乘。也想过对数字求和，但仍然有太多方法可以得到相同的答案。有什么方法可以确保我只有唯一的项目而没有子数组？

我们不能使用子数组（另一个计数器数组等），并且该函数应该运行 O(n)。

如果允许修改输入数组，则问题可以在 O(N) 内解决。

观察结果：

1. 如果数组已排序，那么问题就变得微不足道了。

2. 对值也是 0...N-1 的数组 0...N-1 进行排序也很简单，因为每个元素的位置就是它的值，您可以迭代一次，将元素交换到其最终位置。

只需要在交换期间额外检查该位置的元素i尚未具有该值i，这意味着i在数组中出现两次。

int check(unsigned* a, unsigned size) {
    for (unsigned i = 0; i < size; ++i) {
        unsigned b = a[i];
        if (b != i) {
            do {
                if (b < 0 || b >= size)
                    return false; // value out of range
                unsigned c = a[b];
                if (b == c)
                    return false; // duplicate value
                a[b] = b;
                b = c;
            } while (b != i);
            a[i] = i;
        }
    }
    return true;
}

Note that the the inner loop makes the solution look O(N²), but it's not - each element is visited at most twice. The inner loop is needed to resolve cycles as in {1,2,3,0}.