資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究在 JavaScript 中查詢陣列中的特殊對
問題
我們需要編寫一個 JavaScript 函式，該函式以整數陣列 arr 作為第一個且唯一的引數。
我們的函式應統計滿足以下條件的所有此類索引對 (i, j)：
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) -
二進位制索引樹或 BIT 表示為一個數組。二進位制索引樹的每個節點儲存輸入陣列中某些元素的和。二進位制索引樹的大小等於輸入陣列的大小。
輸出
控制檯中的輸出將為 -
3
更新於： 2021 年 3 月 4 日
96 瀏覽
廣告