c - 在未排序的整数数组中查找缺失元素的计数

Question

如果某些数字重复，如何找出 C 中整数数组中缺少的元素数量？

假设数组是 int array = {1, 2, 1, 5, 4} 并且应该有最多 6 的数字。然后，程序/函数应该输出/返回 2，因为缺少 2 个元素 (3, 6)。

注意:0 不计为缺失数字，也不能出现在数组中。

Answer 1

这边？

int countMissing(int *x, int arrLen, int bound)
{
  int * y = malloc ((bound + 1) * sizeof(int));
  int i  = 0;
  int missing = 0;
  memset(y,0,sizeof(int)*(bound+1));


  for(i = 0; i<arrLen; i++)
  {
    if(x[i]<=bound)
    {
      y[x[i]] = 1;
    }else
    {
       // error handling e.g.
       return -1;
    }

  }

  for(i = 1; i<=bound; i++)
  {
    if(y[i]==0) missing++;
  }

  free(y);
  return missing;
}

用法:

int main(void) 
{
   int array [] = {1, 2, 1, 5, 4};
   printf("%d", countMissing(array, 5, 10));
   return 0;
}

输出:6.