在本教程中，我們將學習計算給定數組中大小為 3 的反轉。
問題陳述 – 我們給出了一個長度為 n 的數組，其中包含不同的數字條目。我們需要找到大小為 3 的數字對的總數，使得 arr[i] > arr[j] > arr[k]，其中 I
在這里，我們將首先學習暴力方法，然后，我們將優化其時間和空間復雜度。
使用暴力方法
在強力方法中，我們將使用三個嵌套的 for 循環來查找大小為 3 的計數反轉。第一個循環對 1 到 n-2 個元素進行迭代，第二個循環從第 i 個元素迭代到第 n-1 個元素。如果前一個元素大于下一個元素，則迭代數組并找到比中間元素小的元素。
語法
用戶可以按照下面的語法使用強力方法來計算給定數組中大小為 3 的反轉。
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 – 如果第 oth 個索引處的元素小于第 n 個索引處的元素，我們可以說我們找到了一個大小為 3 的有效反轉對并增加該值’cnt’ 變量減 1。
第 5 步 – for 循環的所有迭代完成后，返回“cnt”的值。
示例 1
在下面的示例中，我們實現了強力方法來查找大小為 3 的反轉對的總數。
在給定的數組中，用戶只能觀察到輸出中的 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>
登錄后復制
時間和空間復雜度
時間復雜度 – 由于我們使用三個嵌套的 for 循環，時間復雜度為 O(n^3)。
空間復雜度 – 當我們使用常量空間時，空間復雜度為 O(1)。
使用兩個嵌套 for 循環
在這種方法中，我們將使用兩個嵌套循環。我們將找到當前元素右側較小元素的總數，以及左側較大元素的總數。之后，我們將兩者相乘以獲得特定數字的反轉總數。
語法
用戶可以按照下面的語法使用兩個嵌套循環來計算 JavaScript 中大小為 3 的反轉。
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 步 – 將左右變量的值相乘，并將其添加到“cnt”變量中。
示例 2
在下面的示例中，我們使用兩個嵌套循環來查找大小為 3 的反轉總數，如上述方法所示。用戶可以觀察到輸出與第一種方法中的輸出相同。
<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)。
用戶學習了兩種方法來查找給定數組中大小為 3 的計數反轉。在第一種方法中，我們使用暴力方法解決了問題，在第二種方法中，我們進一步優化了解決方案以降低時間復雜度。
以上就是JavaScript 程序計算給定數組中大小為 3 的反轉的詳細內容，更多請關注www.92cms.cn其它相關文章！
