資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究基於輸入陣列在JavaScript中構建比對應元素更小的元素陣列
在JavaScript程式設計領域，構建一個比輸入陣列中對應元素更小的元素陣列的能力具有極其重要的意義。這種有趣的方法允許開發者操作和轉換資料，為創新解決方案和高效演算法開啟大門。透過利用JavaScript陣列操作功能的強大功能，開發者可以生成新的陣列，其元素根據原始陣列的值進行縮小或減少。在本文中，我們將深入探討構建比輸入陣列中對應元素更小的元素陣列的技巧，探索其底層概念，並利用鮮為人知的方法來實現優雅而有效的解決方案。
問題陳述
我們的任務是建立一個JavaScript函式，該函式接收一個數字輸入陣列並根據它構建一個輸出陣列。該函式遍歷輸入陣列的每個元素，並計算小於當前元素但位於其右側的數字數量。輸出陣列的構建方式是，對應索引處的每個元素表示輸入陣列中對應元素右側較小數字的數量。
示例輸入：
Input Array: [5, 2, 6, 1]
示例輸出：
Output Array: [2, 1, 1, 0]
在給定的示例中，輸入陣列為[5, 2, 6, 1]。對於第一個元素5，有兩個數字(2和1)小於5並且出現在輸入陣列中的其右側。類似地，對於第二個元素2，有一個數字(1)小於2並且出現在其右側。對於第三個元素6，有一個數字(1)小於6並且出現在其右側。最後，對於第四個元素1，在其右側沒有小於1的數字。因此，輸出陣列為[2, 1, 1, 0]。
方法
在本文中，我們將看到幾種在JavaScript中解決上述問題陳述的不同方法：
暴力法
二進位制索引樹
二叉搜尋樹
方法1：暴力法
暴力法透過迭代陣列並使用巢狀迴圈比較每對元素來計算輸入陣列中小於每個元素的數字。每當找到較小的數字時，它就會遞增一個計數變數，並將計數儲存在輸出陣列中。由於其巢狀迭代，這種方法的時間複雜度為O(n^2)，其中n是輸入陣列的大小。
示例
countSmallerNumbersToRight函式接受一個輸入陣列並初始化一個空的輸出陣列。它使用兩個巢狀迴圈來迭代輸入陣列中的每個元素，並計算在其右側小於當前元素的數字。外迴圈遍歷每個元素，而內迴圈從下一個元素開始，如果較小則遞增計數。內迴圈針對特定元素完成後，它將計數新增到輸出陣列中。最終，函式返回輸出陣列。
function countSmallerNumbersToRight(inputArray) {
const outputArray = [];
for (let i = 0; i < inputArray.length; i++) {
let count = 0;
for (let j = i + 1; j < inputArray.length; j++) {
if (inputArray[j] < inputArray[i]) {
count++;
}
}
outputArray.push(count);
}
return outputArray;
}
const arr = [6, 2, 8, 5, 1, 3];
console.log(countSmallerNumbersToRight(arr));
輸出
以下是控制檯輸出：
[ 4, 1, 3, 2, 0, 0 ]
方法2：二進位制索引樹
使用二進位制索引樹(Fenwick樹)，這種方法可以有效地計算小於每個元素的數字數量。它建立一個大小等於輸入陣列中最大元素的Fenwick樹，並從右到左遍歷陣列。對於每個元素，它更新Fenwick樹中對應的索引，並使用字首和查詢來計算計數。結果儲存在輸出陣列中，表示每個元素右側較小數字的數量。此方法的時間複雜度為O(n log k)，其中n是輸入陣列的大小，k是陣列中的最大元素。
示例
countSmallerNumbersToRight函式接受一個輸入陣列並定義兩個輔助函式：updateBIT和queryBIT。updateBIT使用索引和值更新二進位制索引樹(BIT)，而queryBIT計算BIT中給定索引之前的累加和。該函式初始化輸入陣列中的最大元素，並建立一個大小為最大元素加一的BIT陣列。然後它從右到左遍歷輸入陣列，查詢BIT以獲取較小數字的計數，並使用當前元素更新BIT。計數新增到outputArray中，該陣列在最後返回。
function countSmallerNumbersToRight(inputArray) {
function updateBIT(BIT, index, value) {
while (index < BIT.length) {
BIT[index] += value;
index += index & -index;
}
}
function queryBIT(BIT, index) {
let count = 0;
while (index > 0) {
count += BIT[index];
index -= index & -index;
}
return count;
}
const maxElement = Math.max(...inputArray);
const BIT = new Array(maxElement + 1).fill(0);
const outputArray = [];
for (let i = inputArray.length - 1; i >= 0; i--) {
outputArray.unshift(queryBIT(BIT, inputArray[i] - 1));
updateBIT(BIT, inputArray[i], 1);
}
return outputArray;
}
const arr = [6, 2, 8, 5, 1, 3];
console.log(countSmallerNumbersToRight(arr));
輸出
以下是控制檯輸出：
[ 4, 1, 3, 2, 0, 0 ]
方法3：二叉搜尋樹
為了使用二叉搜尋樹(BST)計算小於每個元素的數字，建立一個空的BST並初始化輸出陣列。從輸入陣列的倒數第二個元素開始，每個元素都插入到BST中。在插入過程中，跟蹤遇到的較小元素的數量。如果元素小於當前節點，則遞增計數，並在左子樹中遞迴插入元素。如果元素較大，則將計數新增到當前較小元素的數量以及當前節點左側的計數中，並在右子樹中遞迴插入元素。較小元素的數量以相反的順序儲存在輸出陣列中。由於在平衡BST中每個元素的平均插入時間為O(log n)，因此這種方法的時間複雜度為O(n log n)，其中n是輸入陣列的大小。
示例
Node類表示二叉搜尋樹(BST)中的一個節點，並跟蹤節點值、其左側較小元素的數量以及左右子節點。insert函式遞迴地將值插入到BST中，更新遇到的較小元素的數量。如果值較小，則遞增leftCount並在左子樹中遞迴插入它，如有必要則建立一個新節點。如果值較大，則將計數遞增leftCount並在右子樹中插入它，如有必要則建立一個新節點。countSmallerNumbersToRight函式初始化outputArray，建立BST根節點，並將0新增到outputArray中。然後它遍歷輸入陣列，呼叫insert來修改BST並更新outputArray。最後，返回outputArray。
class Node {
constructor(value) {
this.value = value;
this.leftCount = 0;
this.left = null;
this.right = null;
}
}
function insert(node, value, count, outputArray) {
if (value < node.value) {
node.leftCount++;
if (node.left === null) {
node.left = new Node(value);
outputArray.unshift(count);
} else {
insert(node.left, value, count, outputArray);
}
} else {
count += node.leftCount;
if (value > node.value) {
count++;
}
if (node.right === null) {
node.right = new Node(value);
outputArray.unshift(count);
} else {
insert(node.right, value, count, outputArray);
}
}
}
function countSmallerNumbersToRight(inputArray) {
const outputArray = [];
const root = new Node(inputArray[inputArray.length - 1]);
outputArray.push(0);
for (let i = inputArray.length - 2; i >= 0; i--) {
insert(root, inputArray[i], 0, outputArray);
}
return outputArray;
}
const arr = [6, 2, 8, 5, 1, 3];
console.log(countSmallerNumbersToRight(arr));
輸出
以下是控制檯輸出：
[ 4, 1, 3, 2, 0, 0 ]
結論
總之，在JavaScript中基於輸入陣列構建小型元素陣列的過程需要一種細緻入微的方法，這有望增強陣列操作的多功能性。透過利用鮮為人知的方法，例如遞迴演算法或深奧函式，開發者可以生成一個新的陣列，其元素相對於原始陣列中的對應元素具有較小的幅度。這種複雜的方法不僅促進了創造性的問題解決，而且還展示了JavaScript作為程式語言的巨大潛力。因此，透過採用這些鮮為人知的途徑，開發者可以開啟構建具有較小成分的陣列的可能性，為他們的程式碼增添新穎性和獨創性。
87 次檢視
