11

O（1）メモリを備えたマシンがありn、最初のパスで番号を1つずつ渡したいので、2つの番号を除外しn-2て、マシンに番号を渡します。

欠落している数値を見つけるアルゴリズムを作成します。

4

7 に答える 7

11

O（1）メモリで実行できます。

実行中の合計を追跡するために必要なのは、いくつかの整数だけです。整数には log n ビット (n は入力整数の数) は必要ありません。必要なのは 2b+1 ビットだけです。ここで、b は個々の入力整数のビット数です。

最初にストリームを読み取るとき、すべての数値とそのすべての平方を追加します。つまり、入力数値 n ごとに、次の操作を行います。

sum += n
sq_sum += n*n

次に、2 番目のストリームで、2 つの異なる値 sum2 と sq_sum2 に対して同じことを行います。次の計算を行います。

sum - sum2 = a + b
sq_sum - sq_sum2 = a^2 + b^2

(a + b)(a + b) = a^2 + b^2 + 2ab
(a + b)(a + b) - (a^2 + b^2) = 2ab
(sum*sum - sq_sum) = 2ab

(a - b)(a - b) = a^2 + b^2 - 2ab
               = sq_sum - (sum*sum - sq_sum) = 2sq_sum - sum*sum
sqrt(2sq_sum - sum*sum) = sqrt((a - b)(a - b)) = a - b
((a + b) - (a - b)) / 2 = b
(a + b) - b = a

2 つの入力整数の積を格納し、ある場合にはそれらの値の 1 つを 2 倍するため、すべての中間結果に 2b+1 ビットが必要です。

于 2012-04-19T06:43:39.283 に答える
3

数値が 1..N の範囲にあり、そのうちの 2 つが欠落していると仮定するとx、y次のことができます。

ガウスの式を使用します。sum = N(N+1)/2

sum - actual_sum = x + y

数の積を使う:product = 1*2..*N = N!

product - actual_product = x * y

x,y を解決すると、欠落している数値が得られます。

要するに、配列を調べて、各要素を合計して を取得しactual_sum、各要素を乗算して を取得しますactual_product。次に、 の 2 つの方程式を解きxますy。

于 2012-04-18T22:13:03.927 に答える
3

O(1)メモリではできません。

一定kビットのメモリがあると仮定する2^kと、アルゴリズムの可能な状態を持つことができます。

ただし、入力は制限されておらず、ピジョンホールの原則から、さまざまな問題のケース(2^k) + 1に対して可能な回答があると仮定すると、回答が異なる2つの問題に対して同じ回答を2回返すため、アルゴリズムが間違っています。(2^k) + 1

于 2012-04-18T22:14:50.087 に答える
2

質問を読み終えてすぐに次のことが頭に浮かびました。しかし、上記の回答は、O(1) メモリでは不可能であるか、数値の範囲に制約が必要であることを示唆しています。質問に対する私の理解が間違っているかどうか教えてください。よし、これで行こう

O(1)メモリがあります。これは、一定量のメモリがあることを意味します。

n 個の数値が最初に渡されたら、それらを 1 つの変数に追加し続け、別の変数で乗算し続けます。したがって、最初のパスの最後に、2 つの変数S1とP1のすべての数値の合計と積が得られます。これまで 2 つの変数を使用してきました (メモリ内の数値を読み取る場合は +1)。

(n-2)個の数字が 2 回目に渡されたら、同じことを行います。(n-2)個の数値の和と積を、他の 2 つの変数S2とP2に格納します。これまでに 4 つの変数を使用しました (メモリ内の数値を読み取る場合は +1)。

欠落している 2 つの数値がxとyの場合、

x + y = S1 - S2
x*y = P1/P2;

2 つの変数に 2 つの方程式があります。それらを解決します。

したがって、(n に関係なく) 一定量のメモリを使用しています。

于 2012-04-19T06:42:17.117 に答える
1 
void Missing(int arr[], int size)
{
  int xor = arr[0]; /* Will hold xor of all elements */
  int set_bit_no;  /* Will have only single set bit of xor */
  int i;
  int n = size - 2;
  int x = 0, y = 0;

  /* Get the xor of all elements in arr[] and {1, 2 .. n} */
  for(i = 1; i < size; i++)
    xor ^= arr[i];  
  for(i = 1; i <= n; i++)
    xor ^= i;   

  /* Get the rightmost set bit in set_bit_no */
  set_bit_no = xor & ~(xor-1);

  /* Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. */
  for(i = 0; i < size; i++)
  {
    if(arr[i] & set_bit_no)
      x = x ^ arr[i]; /*XOR of first set in arr[] */
    else
      y = y ^ arr[i]; /*XOR of second set in arr[] */
  }
  for(i = 1; i <= n; i++)
  {
    if(i & set_bit_no)
      x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
    else
      y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
  }

  printf("\n The two repeating missing elements are are %d & %d ", x, y);
}
于 2016-06-21T19:41:25.497 に答える