数据结构
网络
关系数据库管理系统 (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 次查看
