c - 如果数组中存在 0 到 n-1 范围内的所有元素，则返回 0 或 1 的函数，运行时间 O(n)

Question

编辑：我忘了提到我不想分配另一个临时数组。

我正在尝试解决 C 中的一个问题，即：假设给你一个数组 a，它的大小为 N。你知道数组中的所有元素都在 0 到 n-1 之间。如果范围（0 到 n-1）中缺少数字，则该函数应该返回 0。否则，它返回 1。正如您所理解的，重复是可能的。问题是它应该在 O(n) 运行时上运行。我想我设法做到了，但我不确定。从这里查看较早的帖子来看，这似乎几乎是不可能的，而且算法似乎比我拥有的算法复杂得多。因此，我觉得有些不对劲。我找不到返回错误输出的输入。

在任何情况下，我都非常感谢您的反馈——或者如果您能想到这可能不起作用的输入。这是代码：

int missingVal(int* a, int size)
{
  int i, zero = 0;
  for (i = 0; i < size; i++)
    //We multiply the element of corresponding index by -1
    a[abs(a[i])] *= -1;

  for (i = 0; i < size; i++)
  {
     //If the element inside the corresponding index is positive it means it never got multiplied by -1 
     //hence doesn't exist in the array
     if (a[i] > 0)
       return 0;

     //to handle the cases for zeros, we will count them
     if (a[i] == 0)
       zero++;
  }
  if (zero != 1)
    return 0;

  return 1;
}

标签： carrays

Answer 1

只需将值复制到另一个数组，将每个值放在其序号位置。然后遍历副本，看看是否缺少任何东西。