Vấn đề
Cần viết hàm JS nhận mảng số nguyên arr. Đếm số cặp chỉ số (i, j) thỏa: i < j và arr[i] > 2 * arr[j].
Ví dụ:
const input = [2, 4, 3, 5, 1];
Kết quả:
const output = 3;
Giải thích:
Ba cặp: [4,1], [3,1], [5,1].
Ví dụ
Mã thực hiện:
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));
Giải thích code:
Sử dụng Binary Indexed Tree (BIT) - cây chỉ số nhị phân. BIT lưu tổng một số phần tử mảng đầu vào. Kích thước BIT = kích thước mảng đầu vào.
Kết quả
Kết quả in ra console:
3