Tìm các cặp đặc biệt trong mảng trong JavaScript

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một mảng Số nguyên, arr, làm đối số đầu tiên và duy nhất.

Hàm của chúng ta sẽ đếm sự xuất hiện của tất cả các cặp chỉ mục như vậy (i, j) thỏa mãn các điều kiện sau -

• I

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

Ví dụ:nếu đầu vào của hàm là -

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

Sau đó, đầu ra phải là -

const output = 3;

Giải thích đầu ra:

Bởi vì ba cặp mong muốn là -

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

Ví dụ

Mã cho điều này sẽ là -

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 mã

Ở đây chúng tôi đã sử dụng Cây được lập chỉ mục nhị phân (BIT) -

Binary Indexed Tree hoặc BIT được biểu diễn dưới dạng một mảng. Cho mảng là BITree []. Mỗi nút của Cây chỉ mục nhị phân lưu trữ tổng của một số phần tử của mảng đầu vào. Kích thước của Cây được lập chỉ mục nhị phân bằng với kích thước của mảng đầu vào.

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

3