JavaScript의 배열에서 독특한 쌍 찾기

문제

첫 번째이자 유일한 인수로 정수 배열인 arr을 취하는 JavaScript 함수를 작성해야 합니다.

우리의 함수는 다음 조건을 충족하는 모든 인덱스 쌍(i, 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(Binary Indexed Tree)를 사용했습니다 -

Binary Indexed Tree 또는 BIT는 배열로 표현됩니다. 배열을 BITree[]로 설정합니다. Binary Indexed Tree의 각 노드는 입력 배열의 일부 요소의 합계를 저장합니다. Binary Indexed Tree의 크기는 입력 배열의 크기와 같습니다.

출력

콘솔의 출력은 -

3