首页  >  文章  >  web前端  >  JavaScript 程序计算给定数组中大小为 3 的反转

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

WBOY
WBOY转载
2023-09-08 11:33:021175浏览

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>

时间和空间复杂度

  • 时间复杂度 - 由于我们使用两个嵌套循环,上述方法的时间复杂度为 O(n^2)。

  • 空间复杂度 - 当我们使用常量空间时,空间复杂度为 O(1)。

用户学习了两种方法来查找给定数组中大小为 3 的计数反转。在第一种方法中,我们使用暴力方法解决了问题,在第二种方法中,我们进一步优化了解决方案以降低时间复杂度。

以上是JavaScript 程序计算给定数组中大小为 3 的反转的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除