BFE.devでのAI解答例 - JavaScript コーディング問題
81. ソートずみの配列をマージする

解答例:

以下は、単純なマージソートのアルゴリズムを使って、複数の配列をマージするJavaScriptのコードです。

function merge(arrays) { // 最初の二つの配列をマージして新しい配列を作成 let merged = mergeArrays(arrays[0], arrays[1]); // それ以降の配列をマージしていく for (let i = 2; i < arrays.length; i++) { merged = mergeArrays(merged, arrays[i]); } return merged; }

// 二つのソート済み配列をマージする function mergeArrays(arr1, arr2) { let merged = []; let i = 0; let j = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] < arr2[j]) { merged.push(arr1[i]); i++; } else { merged.push(arr2[j]); j++; } } // どちらかの配列をすべて追加した後、残りをまるごと追加 while (i < arr1.length) { merged.push(arr1[i]); i++; } while (j < arr2.length) { merged.push(arr2[j]); j++; } return merged; }

このコードの時間複雑度はO(n log n)であり、空間複雑度はO(n)です。最初のマージで、2つの配列を組み合わせて、新しい配列を作るためにn個の要素が必要です。次のマージでは、元の配列の要素を変更せずに、新しい配列を作成するためにn個の要素が必要です。このプロセスを繰り返すことによって、最終的にn個の要素が含まれる配列が作成されます。