arrays - 检查大小为 n 的数组是否包含 0 到 n-1

Question

这是我需要回答的问题：我的程序得到一个大小为 n 的数组，其中包含从 0 到 n-1 的数字。你可以假设我们没有得到低于 0 的数字或高于 n-1 的数字。

我需要检查数组是否包含 0 到 n-1 之间的所有数字，如果包含则返回 1。否则为 0。

例子：

大小为 5 的数组：4,1,0,3,2返回 1。

大小为 5 的数组：4,1,0,3,1返回 0（2 不在数组中）

我试图做的事情：

    int Ex4_bonus() //sort a using a single for loop, then iterate through it with another for loop to look 
{              // for a spot that doesnt equal the value inside it.
    int i,n,boolean=1,temp=0;
    int* a;
    printf("Enter the size of the array\n");
    scanf("%d",&n);
    a=input_array_dyn(a,n);
    printf("Enter numbers from 0-%d\n",n-1);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        if(a[i]!=i)
        {
            temp=a[a[i]];
            a[a[i]]=a[i];
            a[i]=temp;
        }
    }
    for(i=0;i<n;i++)
        if(a[i]!=i)
            boolean=0;
    printf("%d\n",boolean);
    return boolean;
    free(a);
}

但它不适用于某些阵列。我哪里出错了，有没有更好的方法？您不能使用另一个数组，并且程序必须在 O(n) 中运行。

Answer 1

计算 的总和2**a[i]。如果它不等于，(2**n)-1那么您缺少一个元素。

Answer 2

public static boolean arrayCheck(int[] ints) {
for (int i = 0; i < ints.length; i++) {
  while (i != ints[i]) {
    int currPosVal = ints[i];
    if (currPosVal <= i || currPosVal >= ints.length) {
      return false;
    }
    int temp = ints[currPosVal];
    if (currPosVal == temp) {
      return false;
    }
    ints[i] = temp;
    ints[currPosVal] = currPosVal;
  }
}
return true;

}

Answer 3

使用异或运算的特性。

C++：

bool solve(vector<int>& arr){
    int xor = 0;
    for (int i = 1; i < arr.size(); i++)
        xor ^= i;

    for (int  v: arr)
        xor ^= v;

    return xor == 0;
}

或者：

bool solve(vector<int>& arr){
    int xor = 0;
    for (int i = 0; i < arr.size(); i++)
        xor ^= i^arr[i];

    return xor == 0;
}