バイナリ探索木では、2つのノードの順序が逆になります。木の構造を変えずに、正しい二項探索木を復元するアルゴリズムを実装する必要があります。空間O(n)の実装を与えるのは簡単ですが、空間O(1)の実装を与えるにはどうすればよいでしょうか。
忘却の産物の分析
問題
B[i]=A[1]*A[2]*...*A[n]/A[i]配列 A[1..n]が与えられたとき、新しい配列 B[1..n]をO(n)時間で作成しなさい。除算は使えません．
分析
B[i]=A[0]* *A[n]/A[i]B[i]=A[0]* *A[i-1]*A[i+1]* *A[n]要件は除算を使用せずに計算することであり、単純な形の変換により、合計n-1回の乗算が与えられます。各B[i]に対して1回計算すると、全体の計算量はO(n^2)です。これはトピックの要件を満たさないので、乗算の回数を減らす必要があります。乗算回数を減らすには？ 分析を続けると、上記の変換により、B[i]は2つの部分を乗算することで得られます：
A[0]* *A[i-1]
A[i+1]* *A[n]
B[i+1]を計算するとき、B[i]の***部分の結果を使うことが可能です。B[i]にA[i]を掛けるだけで、B[i+1]の***部分が得られます。
A[i+1]*...*A[n]を計算した後、A[i]*A[i+1]*...*A[n]を計算します。A[i]*A[i+1]*...*A[n]はB[i-1]の2番目の部分です。
この分析から、2つの新しい配列が構築されます。
C[i] = A[0]* *A[i-1] = C[i-1]*A[i-1]
D[i] = A[i+1]* *A[n] = D[i+1]*A[i+1}
B[i]=C[i]*D[i]もO(n)です。アルゴリズム全体の時間複雑度はO(n)です。
その答えはここにあります。
まず、A[1]、A[2]、A[3]、A[4]、A[5]の5つの数字だけの配列を見てください。
まずは端から端まで縦断してください：
B[1] = A[1]
B[2] = B[1]*A[2]
B[3] = B[2]*A[3]
B[4] = B[3]*A[4]
B[5] = B[4], 临时变量 C=A[5]
それから端から端まで縦断します：
B[4] = B[3]*C, C=C*A[4]
B[3] = B[2]*C, C=C*A[3]
B[2] = B[1]*C, C=C*A[2]
B[1] = C
アルゴリズムをコード化することは可能です。
