JavaScript 在给定数组中计算大小为三的逆序对

在本教程中，我们将学习如何计算给定数组中大小为三的逆序对。

问题描述 − 我们已经给出一个长度为n的数组，其中包含不同的数值。我们需要找到满足arr[i] > arr[j] > arr[k]条件的大小为三的数对的总数，其中I < j < k。

在这里，我们将首先学习朴素的解决方法，然后优化其时间和空间复杂度。

使用原生的解决方法

在朴素的解决方法中，我们将使用三层嵌套循环来计算大小为三的逆序对。第一层循环从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)，因为我们使用了三层嵌套的循环。
空间复杂度 - 空间复杂度为O(1)，因为我们使用了常数空间。

使用两个嵌套循环

在这个方法中，我们将使用两个嵌套循环。我们将找到当前元素右侧较小元素的总数，并找到左侧较大元素的总数。然后，我们将两者相乘，得到该数字的逆序总数。

语法

用户可以按照以下语法使用两个嵌套循环来计算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 - 将右变量和左变量的值相乘，并将其加到’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>