資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
