JavaScript 程式計算給定數組中大小為 3 的反轉-js教程-PHP中文網

使用暴力方法

文法

演算法

範例 2

時間與空間複雜度

使用兩個巢狀 for 迴圈

首頁

web前端

js教程

JavaScript 程式計算給定數組中大小為 3 的反轉

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Sep 08, 2023 am 11:33 AM

JavaScript 程序计算给定数组中大小为 3 的反转

在本教程中，我們將學習計算給定數組中大小為 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>

登入後複製