JavaScriptで2つの配列から合計が最小となるペアを取り出す方法

問題概要

整数がソート済みの2つの配列 arr1 と arr2 を第1・第2引数として受け取るJavaScript関数を作成する必要があります。

第3引数には数値 num が渡され、num は必ず両方の配列の長さより小さい値になるとします。この関数の役割は、指定された個数(num)のペアを選び出すことです。

各ペアは、1つ目の要素を arr1 から、2つ目の要素を arr2 から取る必要があります。そのうえで、選ばれたペア同士の合計値ができる限り小さくなるように組み合わせを選択しなければなりません。最終的に、関数はこれら(num)個のペアをすべて格納した配列を返します。

例えば、次のような入力が与えられた場合を考えてみましょう。

const arr1 = [1, 1, 2];
const arr2 = [1, 2, 3];
const num = 2;

このとき、期待される出力は次の通りです。

const output = [
    [1, 1], [1, 1]
]

コード例

この問題を解くためのコードは以下の通りです。

const arr1 = [1, 1, 2];
const arr2 = [1, 2, 3];
const num = 2;
const smallestPairs = (arr1 = [], arr2 = [], num = 1) => {
    const temp = Array(arr1.length).fill(0);
    const res = [];
    let compute = () => {
       let flag = Infinity;
       for (let i = 0; i < arr1.length; i++) {
          if (temp[i] < arr2.length && flag > (arr1[i] + arr2[temp[i]])) {
             flag = arr1[i] + arr2[temp[i]];
          }
       }
       if (flag === Infinity || res.length >= num) {
          return;
       } else {
          for (let i = 0; i < arr1.length; i++) {
             if (temp[i] < arr2.length && flag == (arr1[i] + arr2[temp[i]])) {
                res.push(Array.of(arr1[i], arr2[temp[i]]));
                temp[i]++;
             }
          }
          compute();
       }
    }
    compute();
    return res.slice(0, num);
};
console.log(smallestPairs(arr1, arr2, num));

アルゴリズムのポイント

この実装では、各要素ごとに arr2 側の現在位置を記録するポインタ配列 temp を利用しています。処理の流れは以下の通りです。

まず、すべての i について「arr1[i] + arr2[temp[i]]」という合計値を計算し、現時点での最小値 flag を求めます。次に、その最小値と等しい合計を持つすべてのペアを結果配列 res に追加し、該当するポインタを1つ進めます。この操作を再帰的に繰り返すことで、常に合計が小さい順にペアを取り出せる仕組みです。

なお、同じ最小値を持つペアが複数存在する場合は、それらをまとめて1回の処理で登録するため、重複した値(例のように同じ [1, 1] が2つ)も正しく扱えます。最後に slice(0, num) によって、要求された個数ちょうどのペアだけを返しています。

出力結果

コンソールには以下のように表示されます。

[ [ 1, 1 ], [ 1, 1 ] ]