查找数组中是否缺少元素的复杂性 [英] Complexity to find if there is a missing element in an array

问题描述

我正在尝试编写一个函数（用C语言编写），该函数检查数组是否具有所有元素（介于0和 size-1之间）

I am trying to write a function (in C) that checks if an array has all the elements (between 0 and its "size-1")

对于例如，如果数组的大小为3，则它的顺序应为 {0，1，2} 。

For example, if the array's size is 3, it should have {0, 1, 2 } in any order.

问题是：在没有额外数组的情况下执行此操作的最有效复杂度是什么？

The question is: what is the most efficient complexity to do this without an extra array?

我尝试的复杂度如下所示（nlogn + n的平均值） ）。
编辑：对小姐的理解深感抱歉，任何整数都可以作为输入，这意味着无法检查大小-> {0，0，3}

The complexity of my attempt, showed below, is (average of nlogn + n). edit: sorry for the miss understanding, any whole number can be an input, which means checking size wont work --> {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;
}

推荐答案

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

Walk the array using the value [0...n-1] of the element as the next element to visit.

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

As leaving each element, set its value to n. Any visited element with an n has already been visited and so is a failure - unless we have indexed ourselves. Any element with a value outside [0...n-1] is a failure.

访问n后，我们完成了操作。上）。

After 'n' visits we are done. O(n).

不需要排序。这样会消耗该数组。

Sort not needed. This does consume the array.

这篇关于查找数组中是否缺少元素的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！