数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript 程序用于计算给定数组中大小为三的反转次数
在本教程中，我们将学习如何计算给定数组中大小为三的反转次数。
问题陈述 − 我们给定一个长度为 n 的数组，包含不同的数字条目。我们需要找到大小为 3 的数字对的总数，使得 arr[i] > arr[j] > arr[k]，其中 I < j < k。
在这里，我们将首先学习蛮力法，然后我们将优化其时间和空间复杂度。
使用蛮力法
在蛮力法中，我们将使用三个嵌套的 for 循环来查找大小为三的反转次数。第一个循环对 1 到 n-2 个元素进行迭代，第二个循环从第 i 个元素迭代到第 n-1 个元素。如果前一个元素大于后一个元素，则遍历数组并找到小于中间元素的元素。
语法
用户可以遵循以下语法来使用蛮力法计算给定数组中大小为三的反转次数。
for ( ) {
for ( ) {
if (array[m] > array[n]) {
for (let o = n + 1; o < len; o++) {
if (array[n] > array[o])
cnt++;
}
}
}
}
算法
步骤 1 − 使用 for 循环遍历前 n-2 个元素。
步骤 2 − 使用嵌套的 for 循环遍历 m+1 到 len-1 个元素。
步骤 3 − 在嵌套的 for 循环中，检查 array[m] 是否大于 array[n]。如果是，则遍历从第 n+1 个元素到最后一个元素。
步骤 4 − 如果第 0 个索引处的元素小于第 n 个索引处的元素，我们可以说我们找到了一个有效的大小为三的反转对，并将“cnt”变量的值增加 1。
步骤 5 − 一旦 for 循环的所有迭代完成，返回“cnt”的值。
示例 1
在下面的示例中，我们实现了蛮力法来查找大小为三的反转对的总数。
在给定的数组中，用户可以观察到输出中只有 2 个反转对。第一个反转对是 (10, 5, 4)，第二个反转对是 (20, 5, 4)。
<html>
<body>
<h3> Using the <i> Brute force approach </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let len = array.length;
let cnt = 0;
for (let m = 0; m < len - 2; m++) {
for (let n = m + 1; n < len - 1; n++) {
if (array[m] > array[n]) {
for (let o = n + 1; o < len; o++) {
if (array[n] > array[o])
cnt++;
}
}
}
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
时间和空间复杂度
时间复杂度 − 时间复杂度为 O(n^3)，因为我们使用了三个嵌套的 for 循环。
空间复杂度 − 空间复杂度为 O(1)，因为我们使用了常数空间。
使用两个嵌套的 for 循环
在这种方法中，我们将使用两个嵌套循环。我们将找到当前元素右侧较小元素的总数，以及左侧较大元素的总数。之后，我们将两者相乘以获得特定数字的反转总数。
语法
用户可以遵循以下语法来使用两个嵌套循环计算 JavaScript 中大小为三的反转次数。
for ( ) {
// find a smaller element on the right
for ()
if (array[m] < array[n])
right++;
// find bigger elements on the left
for ()
if (array[m] > array[n])
left++;
cnt += right * left;
}
算法
步骤 1 − 使用 for 循环遍历数组的 n 个元素。
步骤 2 − 使用 for 循环查找当前元素右侧所有小于当前元素的元素。
步骤 3 − 再次使用 for 循环查找当前元素左侧所有大于当前元素的元素。
步骤 4 − 将 right 和 left 变量的值相乘，并将其添加到“cnt”变量中。
示例 2
在下面的示例中，我们使用了两个嵌套循环来查找大小为三的反转总数，如上述方法所示。用户可以观察到输出与第一种方法的输出相同。
<html>
<body>
<h3> Using the <i> two nested loops </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let cnt = 0;
let len = array.length;
// Iterate through every element of the array
for (let m = 0; m < len - 1; m++) {
// count all element that are smaller than arr[m] and at the right to it
let right = 0;
for (let n = m - 1; n >= 0; n--)
if (array[m] < array[n])
right++;
// count all element that are greater than arr[m] and at the left to it
let left = 0;
for (let n = m + 1; n < len; n++)
if (array[m] > array[n])
left++;
// multiply left greater and right smaller elements
cnt += right * left;
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
时间和空间复杂度
时间复杂度 − 上述方法的时间复杂度为 O(n^2)，因为我们使用了两个嵌套循环。
空间复杂度 − 空间复杂度为 O(1)，因为我们使用了常数空间。
用户学习了两种方法来查找给定数组中大小为三的反转次数。在第一种方法中，我们使用蛮力法解决了问题，在第二种方法中，我们进一步优化了解决方案以降低时间复杂度。
129 次查看
