algorithm - トリッキーなアルゴリズムの質問

Question

重複の可能性:
数値の配列で不足している数値を見つける最も簡単な方法

入力: ソートされていない配列 A[1,..,n] には、範囲 0、..、n の整数のうち 1 つを除くすべてが含まれます

問題は、不足している整数を O(n) 時間で決定することです。A の各要素は 2 進数で表され、利用可能な唯一の操作は関数 bit(i, j) です。これは、A[i] の j 番目のビットの値を返し、一定の時間がかかります。

何か案は？ある種の分割統治アルゴリズムが適切だと思いますが、正確に何をすべきかわかりません。前もって感謝します！

score 9 · Accepted Answer

1との間の数の合計がであるという数学的なn性質nですn(n+1)/2。あなたはこれを見ることができます10：

  1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
= (1+10) + (2+9) + (3+8) +(4+7) + (5+6)
= 11 + 11 + 11 + 11 + 11
= 55

したがって、拡張により、はからまでの数値の合計です。これは、0それにn0 を追加するだけだからです。したがって、すべての数値を合計してカウントを維持し、その式を使用して不足している数値を見つけます。

したがって、次のようなものです：

count = 0
sum = 0
foreach num in list:
    sum = sum + num
    count = count + 1
missing = count * (count+1) / 2 - sum

で数値を取得するのbit(i,j)は難しいため、ビットを個別に抽出し、合計するために実際の数値に変換する必要があります。

score 7 · Accepted Answer

加算よりも高速な XOR 演算子を使用できます。各ビットにアクセスできるので、ここでビットごとの XOR を実行します。ここで使用される原則は (A XOR B XOR A ) = B

例: (1 XOR 2 XOR 3) XOR (1 XOR 2) = 3

for i=0 to n
{
Total=Total XOR i
}

foreach element in A
{
Total=Total XOR element
}

score 0 · Accepted Answer

ビットメソッドを使用すると、各数値の各ビットを循環させるだけで済みます。つまり、自動的に O(n*j) になるため、j は n を表すビット数です。

ビットメソッドを使用しないソリューションが許可されていると仮定すると、paxdiablo はそれを理解していると思います。

3 に答える 3