在C中检查数组中是否有从0到长度-1的数字

Question

我有一项作业，如果您能帮我解决一个问题，我会很高兴在这个作业中，我有一个这样的问题:

编写一个接收数组及其长度的函数。该函数的目的是检查数组是否包含从 0 到 length-1 的所有数字，如果包含，则函数将返回 1 或 0，否则返回。该函数只能遍历数组一个。您无法对数组进行排序或在函数中使用计数数组

我编写了计算数组值和索引的总和与乘积的函数

int All_Num_Check(int *arr, int n)
{
 int i, index_sum = 0, arr_sum = 0, index_multi = 1, arr_multi = 1;

 for (i = 0; i < n; i++)
  {
    if (i != 0)
       index_multi *= i;
    if (arr[i] != 0)
       arr_multi *= arr[i];

    index_sum += i;
    arr_sum += arr[i];
  }

 if ((index_sum == arr_sum) && (index_multi == arr_multi))
    return 1;

 return 0;
}

即:length = 5, arr={0,3,4,2,1} - 这是一个正确的数组length = 5 , arr={0,3,3,4,2} - 这不是正确的数组

不幸的是，这个函数在所有不同的数字变化情况下都不能正常工作。即:长度 = 5 , {1,2,2,2,3}

谢谢你的帮助。

Answer 1

正如你的反例所示，检查总和和乘积是不够的。

一个简单的解决方案是对数组进行排序，然后检查每个位置i，a[i] == i。

编辑:原始问题已被编辑，因此排序也被禁止。假设所有数字都是正数，以下解决方案通过对相应索引求反来“标记”所需范围内的数字。如果任何数组单元格已经包含标记的数字，则意味着我们有一个重复的数字。

int All_Num_Check(int *arr, int n) {
  int i, j;

  for (i = 0; i < n; i++) {
      j = abs(arr[i]);
      if ((j >= n) || (arr[j] < 0)) return 0;  
      arr[j] = -arr[j];
  }

  return 1;
}