在 JavaScript 中查找数组中的特殊对
javascriptweb developmentfront end technology
问题
我们需要编写一个 JavaScript 函数，该函数将整数数组 arr 作为第一个也是唯一的参数。
我们的函数应该计算满足以下条件的所有索引对 (i, j) 的出现次数 −
I < j, and
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
