检查数组是否包含 0 到 n-1 之间的所有整数的有效方法

Question

关于我之前的 post： --> 我正在尝试解决一个算法，以最有效的方式检查数组是否包含 0 和 n - 1 之间的所有元素（时间复杂度方面）没有额外的数组，。我想出了两个解决方案。你能帮我确定哪个更有效率吗？我应该交哪一个？谢谢你。

/* first attempt */

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

    for (i = 0; i < n; i++)
    {
        if (a[i] < 0 || a[i] >= n) //check for unwanted integers
            return 0;

        while (i != a[i])
        {
            swap(&a[a[i]], &a[i]); //puts numbers in their index

            flag++;
            if (flag > 1 && a[i] == a[a[i]]) //check for duplicates
                return 0;
        }
        flag = 0;
    }

    return 1;
}


/* second attempt */

int check_missing_b(int *a, int n)
{
    int i, sum_a = 0, sum_i = 0, sum_aa = 0, sum_ii = 0;

    for (i = 0; i < n; i++)
    {
        if (a[i] < 0 || a[i] >= n) //check for unwanted integers
            return 0;

        else
        {
            sum_a += a[i]; // sum of 'elements' should be equal to sum of 'i' 
            sum_i += i;

            sum_aa += a[i] * a[i]; // multiplication sum of 'elements' should be equal to multiplication sum of 'i' 
            sum_ii += i * i;
        }
    }
    return (sum_aa == sum_ii && sum_a == sum_i);
}

Answer 1

首先，我们需要修复 check_missing_a，因为它有问题。交换后，a[i] 可能超出跟随 a[a[i]] 的界限。固定版本：

int check_missing_a2(int *a, int n) {
    for (int i = 0; i < n; ++i) {
        while (i != a[i]) {
            if (a[i] < i || a[i] >= n || a[i] == a[a[i]])
                return 0;

            swap(&a[i], &a[a[i]]);
        }
    }

    return 1;
}

我们甚至可以保存一些比较如下：（感谢@chmike）

int check_missing_a2(int *a, int n)
{
    for (int i = 0; i < n; ++i)
        if (a[i] < 0 || a[i] >= n)
            return 0;

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

            swap(&a[i], &a[a[i]]);
        }
    }

    return 1;
}

check_missing_a2

的复杂度

乍一看，可能会认为 check_missing_a2 比 O(N) 慢，因为外层循环执行了 N 次，还有另一个内层循环。

然而，内循环最多执行N-1次交换。例如，下图说明了 N=8 时 0..N-1 中数字的每种排列的交换次数：

# swaps   # arrangements
-------   --------------
      0                1
      1               28
      2              322
      3             1960
      4             6769
      5            13132
      6            13068
      7             5040

正如@4386427 所解释的，每次交换都会将至少一个元素放置在正确的位置。因此不能超过 N 次交换。

这意味着函数的任何部分都不会执行超过 2*N 次，因此复杂度为 O(N)。

check_missing_b

的复杂度

具有 N 遍的单个循环，复杂度为 O(N)。

至于实际性能，我怀疑 check_missing_a2 总是比 check_missing_b 快。

当然还有check_missing_a2改变数组，check_missing_b溢出的问题。

Answer 2

函数check_missing_b绝对是O(n)，因为它只有一个循环。它还有属性不修改输入数组 a。但是，它在 n 的大小上有限制，因为 sum_ii 可能会溢出。

函数check_missing_a有两个循环，分析起来不太明显。它还对数组 a 中的值进行排序，从而修改输入数组。这可能是个问题。另一方面，它不会溢出，这是优于其他功能的优势。

此函数是基数排序，因为每次交换都会在其最终位置放置一个值。交换次数将少于 n。因此这个函数是 O(n).

不幸的是，这个功能也有问题。当 a[i] > i 时，值 a[a[i]] 可能大于 n。因此，该功能需要两次传递元素。第一遍确保没有值小于 0 且大于 n-1。第二遍进行基数排序。

这是我建议的函数实现 check_missing_a。

int check_missing_c(int *a, int n)
{
    for (int i = 0; i < n; i++)
        if (a[i] < 0 || a[i] >= n)
            return 0;
    for (int i = 0; i < n; i++)
        while (i != a[i]) {
            if (a[i] == a[a[i]])
                return 0;
            int tmp = a[i];
            a[i] = a[tmp];
            a[tmp] = tmp;
        }
    return 1;
}

检查数组是否包含 0 到 n-1 之间的所有整数的有效方法

efficient way to check if an array has all integers between 0 and n-1

c

arrays

complexity-theory