JavaScriptで配列の欠落した数値を補完し等差数列を完成させる方法

今回は、n 個の要素からなる配列が与えられます。そのうち数値が入っているのは 2 つだけで、残りはすべて null です。イメージは次のようなものです。

const arr = [null, null, -1, null, null, null, -3, null, null, null];

この配列を受け取り、含まれている 2 つの数値をもとに等差数列を完成させて、null の部分を適切な数値で埋める関数を作成します。分かりやすく言い換えると、null は空欄であり、そこに数値を書き込んで配列全体を等差数列に仕上げる必要がある、ということです。

等差数列とは

数列(配列)において、任意の n 番目の値が「(n−1) 番目の値に定数 d を加えたもの」になっているとき、その数列は等差数列をなしていると言います。

例:

1, 2, 3, 4, 5, 6, 7, 8

この例では、後続の各数値は直前の数値に定数(ここでは 1)を加えることで得られています。

その他の例:

1, 1, 1, 1, 1, 1, 1, 1, 1
10, 8, 6, 4, 2, 0, -2

こうした数列では、慣習的に初項を a、隣り合う項の差である公差を d で表します。

したがって、n 番目の項を Tn と表すと、次の一般項の公式が成り立ちます。

Tn = a + (n - 1)d

ここで n は、その数値の 1 起点のインデックスです。

実装の考え方

前提が整理できたところで、コードを書いていきましょう。まず配列から初項(a)と公差(d)を求めます。これらが判明すれば、あとは元の配列に対してループを回し、数列を生成するだけです。

手順のポイント

• null 以外の要素を走査し、最初に見つかった数値と最後の数値を、それぞれのインデックスとともに記録します。
• 2 つの既知の値とそのインデックスの差から、公差 d を計算できます。
• 初項 a は、「既知の値 −(インデックス × 公差)」で求められます。
• 最後に map を使えば、各インデックスに対応する等差数列の値を一括生成できます。

コード例

const arr = [null, null, -1, null, null, null, -3, null, null, null];
const arr2 = [null, null, -1, null, null, null, 12, null, null, null,
null, null, null];
const constructSeries = (arr) => {
   const map = {
      first: undefined,
      last: undefined
   };
   arr.forEach((el, ind) => {
      if(el !== null){
         if(map['first']){
            map['last'] = [el, ind];
         }else{
            map['first'] = [el, ind];
         }
      };
   });
   const { first, last } = map;
   const commonDifference = (last[0] - first[0])/(last[1] - first[1]);
   const firstElement = (first[0]) - ((first[1])*commonDifference);
   return arr.map((item, index) => {
      return firstElement + (index * commonDifference);
   });
};
console.log(constructSeries(arr));
console.log(constructSeries(arr2));

出力結果

コンソールには次のように出力されます。

[
   0, -0.5, -1, -1.5,
   -2, -2.5, -3, -3.5,
   -4, -4.5
]
[
   -7.5, -4.25, -1,
   2.25, 5.5, 8.75,
   12, 15.25, 18.5,
   21.75, 25, 28.25,
   31.5
]

まとめ

このように、2 つの既知の値とその位置情報さえあれば、等差数列の一般項 Tn = a + (n − 1)d を利用することで、配列中のすべての null を正しい数値で補完できます。配列を数回走査するだけの O(n) の処理で済むため、大きな配列でも効率的に動作します。小数を含む等差数列にも対応している点も実用上便利です。