BFE.devでのAI解答例 - JavaScript コーディング問題
25. 配列の順序を変える

空間複雑度がO(1)で解決する方法は、A配列内で要素の入れ替えを行うことです。具体的には、B[i]で指定された位置にある要素A[i]と、その要素が移動先となる位置にある要素A[B[i]]を交換します。この操作をB配列の全ての要素について行うことで、A配列の順序が変わります。

以下が実装例です。

const A = ['A', 'B', 'C', 'D', 'E', 'F']
const B = [1,   5,   4,   3,   2,   0]

for (let i = 0; i < A.length; i++) {
  // B[i]が現在の位置にある要素の移動先
  let j = B[i]
  
  // A[i]とA[j]を交換
  const tmp = A[i]
  A[i] = A[j]
  A[j] = tmp

  // Bの更新：A[j]が移動済みなので、移動先はiとなる
  B[j] = i
}

console.log(A) // ['F', 'A', 'E', 'D', 'C', 'B']

この実装では、A[i]とA[j]を交換するための一時的な変数tmpだけが追加的なメモリを必要とします。それ以外の領域使用量は入力サイズに依存しないため、空間複雑度がO(1)となります。