JavaScriptで配列内の特異なペア(i < j かつ arr[i] > 2*arr[j])を効率的に数える方法

問題

整数の配列 arr を唯一の引数として受け取る JavaScript 関数を作成する必要があります。

この関数は、次の2つの条件を両方とも満たすインデックスのペア (i, j) の出現回数を数えて返します。

• i < j であること
• arr[i] > 2 * arr[j] であること

たとえば、関数への入力が次のような場合を考えてみましょう。

const input = [2, 4, 3, 5, 1];

このとき、期待される出力は次のようになります。

const output = 3;

出力の説明

これは、条件を満たすペアが次の3つ存在するためです。

[4, 1], [3, 1], [5, 1]

サンプルコード

この問題を実装したコードは以下の通りです。

const arr = [2, 4, 3, 5, 1];
const peculiarPairs = (arr = []) => {
    let count = 0;
    let copy = arr.slice().sort((a,b)=> a - b);
    let bit = new Array(arr.length+1).fill(0);
    for (const num of arr){
        count += search(bit, indexed(copy, 2*num+1));
        bit = insert(bit, indexed(copy, num));
    };
    return count;
};
const search = (bit, i) => {
    let sum = 0;
    while (i < bit.length){
        sum += bit[i];
        i += i & -i;
    }
    return sum;
}
const insert = (bit, i) => {
    while (i > 0){
        bit[i] += 1;
        i -= i & -i;
    }
    return bit;
}
const indexed = (arr, val) => {
    let l = 0, r = arr.length-1, m = 0;
    while (l <= r) {
        m = l + ((r-l) >> 1);
        if (arr[m] >= val){
            r = m-1;
        }else{
            l = m+1;
        }
    }
    return l+1;
}
console.log(peculiarPairs(arr));

コードの解説

この実装では、Binary Indexed Tree(BIT、二分インデックス木)と呼ばれるデータ構造を使用しています。

BIT(「フェニック木」とも呼ばれます)は配列として表現されます。ここでは BITree[] という名前の配列を想定します。Binary Indexed Tree の各ノードには、入力配列の一部の要素の合計値が格納されており、ツリー全体のサイズは入力配列のサイズと等しくなります。

このデータ構造を活用することで、要素の挿入や累積頻度の検索をそれぞれ O(log n) の計算量で処理できます。その結果、すべてのペアを総当たりで調べる単純な二重ループ(O(n²))に比べ、大規模な配列でも大幅に高速にペアを数えることが可能です。

出力

上記のコードを実行すると、コンソールには次のように出力されます。

3