Home > Article > Web Front-end > JavaScript program to calculate the inversion of size 3 in a given array

JavaScript program to calculate the inversion of size 3 in a given array

WBOYforward: 2023-09-08 11:33:021177browse

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

In this tutorial, we will learn to calculate the inversion of size 3 in a given array.

Problem Statement - We are given an array of length n containing distinct numeric entries. We need to find the total number of pairs of numbers of size 3 such that arr[i] > arr[j] > arr[k], where I

Here, we will first learn the brute force method, and then, we will optimize its time and space complexity.

Use brute force methods

In the brute force approach, we will use three nested for loops to find count reversals of size 3. The first loop iterates from 1 to n-2 elements, and the second loop iterates from the i-th element to the n-1-th element. If the previous element is greater than the next element, iterate over the array and find the element smaller than the middle element.

grammar

Users can use the brute force method following the syntax below to compute the inversion of size 3 in a given array.

for ( ) {
   for ( ) {
      if (array[m] > array[n]) {
         for (let o = n + 1; o < len; o++) {
            if (array[n] > array[o])
            cnt++;
         }
      }
   }
}

algorithm

Step 1 - Iterate over the first n-2 elements using a for loop.
Step 2 - Iterate over m 1 to len-1 elements using a nested for loop.
Step 3 - In the nested for loop, check if array[m] is greater than array[n]. If so, iterate from the n 1th element to the last element.
Step 4 - If the element at the othth index is smaller than the element at the nth index, we can say that we found a valid inversion pair of size 3 and increase that The value 'cnt' variable is decremented by 1.
Step 5 - After all iterations of the for loop are completed, return the value of "cnt".

Example 1

In the example below, we implement a brute force method to find the total number of reversal pairs of size 3.

In the given array, the user can only observe 2 inversion pairs in the output. The first reversal pair is (10,5,4) and the second reversal pair is (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>

Time and space complexity

Time complexity - Since we use three nested for loops, the time complexity is O(n^3).
Space complexity - When we use constant space, the space complexity is O(1).

Use two nested for loops

In this method, we will use two nested loops. We will find the total number of smaller elements to the right of the current element, and the total number of larger elements to the left. After that, we multiply the two to get the total number of reversals for a specific number.

grammar

Users can use two nested loops to calculate reversals of size 3 in JavaScript by following the syntax below.

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;
}

algorithm

Step 1 - Iterate over n elements of the array using a for loop.
Step 2 - Use a for loop to find all elements to the right of the current element that are smaller than the current element.
Step 3 - Use the for loop again to find all elements to the left of the current element that are larger than the current element.
Step 4 - Multiply the values of the left and right variables and add them to the "cnt" variable.

Example 2

In the following example, we use two nested loops to find the total number of reversals of size 3, as shown in the above method. The user can observe that the output is the same as in the first method.

<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>

Time and space complexity

Time complexity - Since we use two nested loops, the time complexity of the above method is O(n^2).
Space complexity - When we use constant space, the space complexity is O(1).

The user learned two methods to find count inversions of size 3 in a given array. In the first approach, we solved the problem using a brute force approach, and in the second approach, we further optimized the solution to reduce the time complexity.

The above is the detailed content of JavaScript program to calculate the inversion of size 3 in a given array. For more information, please follow other related articles on the PHP Chinese website!

JavaScript Array 常量 for 循环 len 算法

Statement：

This article is reproduced at:tutorialspoint.com. If there is any infringement, please contact admin@php.cn delete

Previous article：Who needs AMP? Simplify the process of lazy loading responsive images with Layzr.jsNext article：Who needs AMP? Simplify the process of lazy loading responsive images with Layzr.js

See more

JavaScript program to calculate the inversion of size 3 in a given array

Use brute force methods

grammar

algorithm

Example 1

Time and space complexity

Use two nested for loops

grammar

algorithm

Example 2

Time and space complexity

Related articles