ปัญหา
รับอาร์เรย์ arr นับคู่ดัชนี (i, j) ที่ i < j และ arr[i] > 2 * arr[j]
ตัวอย่าง
const input = [2, 4, 3, 5, 1];
คู่ที่ตอบโจทย์: [4,1], [3,1], [5,1] → ผลลัพธ์ 3
โค้ดตัวอย่าง (Binary Indexed Tree / Fenwick Tree)
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 (Fenwick Tree) นับจำนวนค่าที่น้อยกว่าเงื่อนไขอย่างมีประสิทธิภาพ
ผลลัพธ์
3
