查找数组中是否缺少元素的复杂性

Question

我正在尝试编写一个函数(用 C 语言)来检查数组是否包含所有元素(在 0 和它的“size-1”之间)

例如，如果数组的大小是 3，它应该有 {0, 1, 2 }以任何顺序。

问题是:在没有额外数组的情况下，最有效的复杂性是什么？

如下所示，我尝试的复杂性是(nlogn + n 的平均值)。
编辑:对不起，理解失误，任何整数都可以作为输入，这意味着检查大小不起作用 --> {0, 0, 3}

int check_missing_element(int *a, int n)
{
    int i = 0;

    quicksort(a, 0, n - 1);

    for (i = 0; i < n; i++)
    {
        if (a[i] != i)
            return 0;
    }

    return 1;
}

Answer 1

使用元素的值 [0...n-1] 作为下一个要访问的元素遍历数组。

离开每个元素时，将其值设置为 n .任何带有 n 的访问过的元素已经被访问过，所以失败了——除非我们已经索引了自己。任何值在 [0...n-1] 之外的元素都是失败的。

在“n”次访问之后，我们完成了。在)。

排序不需要。这确实消耗了数组。