2

配列a[]には、1 つを除いて 0 から N までのすべての整数が含まれます。ただし、単一の操作で要素にアクセスすることはできません。代わりに、get(i, k)の k 番目のビットを返すを呼び出すか、 の i 番目と j 番目の要素を交換するa[i]を呼び出すことができます。欠落している整数を見つける O(N) アルゴリズムを設計します。(簡単にするために、N は 2 のべき乗であると仮定します。)swap(i, j)a[]

4

6 に答える 6

9

N が 2 の累乗の場合、分割統治O(N)法を使用して実行できます。

logN数値にはビットがあることに注意してください。ここで、この情報を使用して、パーティション ベースの選択アルゴリズムとradix-sortを組み合わせて使用​​できます。

  1. 最初のビットの数値を反復し、配列を 2 つの半分に分割します。前半はこのビットが 0 で、残りの半分は 1 です (swap()配列の分割には を使用します)。
  2. 一方の半分にはceil(N/2)要素があり、もう一方にはfloor(N/2)要素があることに注意してください。
  3. 欠落している数値が見つかるまで、小さい方の配列に対してこのプロセスを繰り返します。

このアプローチの複雑さは になるのでN + N/2 + N/4 + ... + 1 < 2N、O(n)

于 2012-09-13T10:27:44.267 に答える
3

O(N*M)、M はビット数です。

N は 2 のべき乗で、欠落している数は 1 つだけなので、各ビットを調べて、そのビットが 0 の数と 1 の数を数えると、2^(M-1) と 2^ が得られます。 (M-1)-1、短い方が欠損数に属します。これにより、欠落している数のすべてのビットを取得できます。

于 2012-09-13T09:30:31.913 に答える
1

スワップ操作も必要ありません!! XORを使用してください！さて、最初に0からNまでのすべての数値のバイナリXORを計算できます。

long nxor = 0;
for (long i = 0; i <= N; i++)
    nxor = XOR(nxor, i);

次に、配列内のすべての数値のXORを計算できます。これも簡単です。Kと呼びましょう-すべての数の中の最大ビット数。

long axor = 0;

long K = 0;
long H = N;
while (H > 0)
{
   H >>= 1; K++;
}

for (long i = 0; i < N - 1; i++)
   for (long j = 0; j < K; k++)
    axor = XOR(axor, get(i,j) << j);

最後に、結果のXORを計算できます。

long result = XOR(nxor, axor).

ちなみに、nが2の累乗の場合、nxor値はnに等しくなります;-)！

于 2012-09-13T11:22:04.647 に答える
0

入力が であると仮定するとa[]=0,1,2,3,4,5,7,8、それ6が欠落しています。数値は、ソリューションが機能するために並べ替える必要がないため、便宜上のみ並べ替えられています。

それ以来、数値はビットを使用して表されNます。からまで。8400001000

最初に、最上位ビットを使用して配列を分割します。

と を取得0,1,2,3,4,5,7し8ます。が存在するので8、左側のパーティションに進みます。

2 番目の最上位ビットを使用してサブ配列を分割します。

と を取得0,1,2,3し4,5,7ます。次に、要素数が奇数のパーティションに進みます。これは4,5,7です。

3 番目の最上位ビットを使用してサブ配列を分割します。

と を取得4,5し7ます。再び奇数の要素を持つパーティションを続行します。これは7です。

得られた 4 番目の最上位ビットと を使用してサブ配列を分割しnothingます7。

したがって、欠けている数は6です。

もう一つの例：

  • a[]=0,1,3,4,5,6,7,8、それが2ありません。
  • 第 1 ビット パーティション:0,1,3,4,5,6,7および8に進み0,1,3,4,5,6,7ます。
  • 2 番目のビット パーティション:0,1,3および、 (奇数の要素)4,5,6,7に進みます。0,1,3
  • 3 番目のビット パーティション:0,1および、 (要素の奇数)3に進みます。3
  • 4 番目のビット パーティション:nothingと3が2欠落しています。

もう一つの例：

  • a[]=1,2,3,4,5,6,7,8、それが0ありません。
  • 第 1 ビット パーティション:1,2,3,4,5,6,7および8に進み1,2,3,4,5,6,7ます。
  • 2 番目のビット パーティション:1,2,3および、 (奇数の要素)4,5,6,7に進みます。1,2,3
  • 3 番目のビット パーティション:1および、 (要素の奇数)2,3に進みます。1
  • 4 番目のビット パーティション:nothingと1が0欠落しています。

最初のパーティションはN操作を行います。2 番目のパーティションはN操作を行います。3 番目のパーティションはN/2操作を行います。4 番目のパーティションはN/4操作を行います。等々。

したがって、実行時間は O(N+N+N/2+N/4+...)=O(N) です。

于 2012-09-13T12:52:41.780 に答える
0

また、xor 操作の代わりに sum 操作を使用する場合の別の答えも示します。すぐ下のコードを見つけてください。

long allsum = n * (n + 1) / 2;
long sum = 0;

long K = 0;
long H = N;
while (H > 0)
{
   H >>= 1; K++;
}

for (long i = 0; i < N - 1; i++)
   for (long j = 0; j < K; k++)
    sum += get(i,j) << j;

long result = allsum - sum.
于 2012-09-13T11:26:39.873 に答える
0

操作なしでは、このxorようにこの質問に答えます

package missingnumberinarray;
public class MissingNumber 
{
    public static void main(String args[])
    {
        int array1[] = {1,2,3,4,6,7,8,9,10}; // we need sort the array first.
        System.out.println(array1[array1.length-1]);
        int n = array1[array1.length-1];
        int total = (n*(n+1))/2;
        System.out.println(total);
        int arraysum = 0;
        for(int i = 0; i < array1.length; i++)
        {
            arraysum += array1[i];
        }
        System.out.println(arraysum);
        int mis = total-arraysum;
        System.out.println("The missing number in array is "+mis);
    }
}
于 2013-04-30T05:08:07.363 に答える