在JavaScript中查找数组中的奇异对

问题

我们需要编写一个JavaScript函数，该函数接受一个整数数组arr作为第一个也是唯一的参数。

我们的函数应计算满足以下条件的所有此类索引对(i,j)的出现-

• 我<j，并且

• arr [i]> 2 * arr [j]

例如，如果函数的输入为-

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

那么输出应该是-

const output = 3;

输出说明：

因为三个所需的对是-

[4, 1], [3, 1] and [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));

代码说明

我们在这里使用了二进制索引树(BIT)-

二进制索引树或BIT表示为一个数组。令数组为BITree []。二叉索引树的每个节点都存储输入数组中某些元素的总和。二进制索引树的大小等于输入数组的大小。

输出结果

控制台中的输出将是-

3