1

答える必要のある質問は次のとおりです。私のプログラムは、0からn-1までの数値を含むサイズnの配列を取得します。0未満の数値またはn-1を超える数値は取得されないと想定できます。

配列に0からn-1までのすべての数値が含まれているかどうかを確認し、含まれている場合は1を返す必要があります。それ以外の場合は0。

例：

サイズ5の配列：4,1,0,3,21を返します。

サイズ5の配列：4,1,0,3,10を返します（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）で実行する必要があります。

4

3 に答える 3

1

の合計を計算し2**a[i]ます。等しくない場合(2**n)-1は、要素がありません。

于 2012-12-24T18:37:59.870 に答える
0

xor 演算の特性を利用します。

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;
}
于 2021-07-17T14:33:58.490 に答える