Dada una array arr[] de tamaño n. Tres elementos arr[i], arr[j] y arr[k] forman una inversión de tamaño 3 si a[i] > a[j] >a[k] e i < j < k. Encuentre el número total de inversiones de tamaño 3.
Ejemplo :
Input: {8, 4, 2, 1} Output: 4 The four inversions are (8,4,2), (8,4,1), (4,2,1) and (8,2,1). Input: {9, 6, 4, 5, 8} Output: 2 The two inversions are {9, 6, 4} and {9, 6, 5}
Ya hemos discutido el conteo de inversión del tamaño dos por ordenación por fusión , Self Balancing BST y BIT .
Enfoque simple: realice un bucle para todos los valores posibles de i, j y k y verifique la condición a[i] > a[j] > a[k] e i < j < k.
C++
// A Simple C++ O(n^3) program to count inversions of size 3 #include<bits/stdc++.h> using namespace std; // Returns counts of inversions of size three int getInvCount(int arr[],int n) { int invcount = 0; // Initialize result for (int i=0; i<n-2; i++) { for (int j=i+1; j<n-1; j++) { if (arr[i]>arr[j]) { for (int k=j+1; k<n; k++) { if (arr[j]>arr[k]) invcount++; } } } } return invcount; } // Driver program to test above function int main() { int arr[] = {8, 4, 2, 1}; int n = sizeof(arr)/sizeof(arr[0]); cout << "Inversion Count : " << getInvCount(arr, n); return 0; }
Java
// A simple Java implementation to count inversion of size 3 class Inversion{ // returns count of inversion of size 3 int getInvCount(int arr[], int n) { int invcount = 0; // initialize result for(int i=0 ; i< n-2; i++) { for(int j=i+1; j<n-1; j++) { if(arr[i] > arr[j]) { for(int k=j+1; k<n; k++) { if(arr[j] > arr[k]) invcount++; } } } } return invcount; } // driver program to test above function public static void main(String args[]) { Inversion inversion = new Inversion(); int arr[] = new int[] {8, 4, 2, 1}; int n = arr.length; System.out.print("Inversion count : " + inversion.getInvCount(arr, n)); } } // This code is contributed by Mayank Jaiswal
Python3
# A simple python O(n^3) program # to count inversions of size 3 # Returns counts of inversions # of size threee def getInvCount(arr): n = len(arr) invcount = 0 #Initialize result for i in range(0,n-1): for j in range(i+1 , n): if arr[i] > arr[j]: for k in range(j+1 , n): if arr[j] > arr[k]: invcount += 1 return invcount # Driver program to test above function arr = [8 , 4, 2 , 1] print ("Inversion Count : %d" %(getInvCount(arr))) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// A simple C# implementation to // count inversion of size 3 using System; class GFG { // returns count of inversion of size 3 static int getInvCount(int []arr, int n) { // initialize result int invcount = 0; for(int i = 0 ; i < n - 2; i++) { for(int j = i + 1; j < n - 1; j++) { if(arr[i] > arr[j]) { for(int k = j + 1; k < n; k++) { if(arr[j] > arr[k]) invcount++; } } } } return invcount; } // Driver Code public static void Main() { int []arr = new int[] {8, 4, 2, 1}; int n = arr.Length; Console.WriteLine("Inversion count : " + getInvCount(arr, n)); } } // This code is contributed by anuj_67.
PHP
<?php // A O(n^2) PHP program to // count inversions of size 3 // Returns count of // inversions of size 3 function getInvCount($arr, $n) { // Initialize result $invcount = 0; for ($i = 1; $i < $n - 1; $i++) { // Count all smaller elements // on right of arr[i] $small = 0; for($j = $i + 1; $j < $n; $j++) if ($arr[$i] > $arr[$j]) $small++; // Count all greater elements // on left of arr[i] $great = 0; for($j = $i - 1; $j >= 0; $j--) if ($arr[$i] < $arr[$j]) $great++; // Update inversion count by // adding all inversions // that have arr[i] as // middle of three elements $invcount += $great * $small; } return $invcount; } // Driver Code $arr = array(8, 4, 2, 1); $n = sizeof($arr); echo "Inversion Count : " , getInvCount($arr, $n); // This code is contributed m_kit ?>
Javascript
<script> // A simple Javascript implementation to count inversion of size 3 // returns count of inversion of size 3 function getInvCount(arr, n) { let invcount = 0; // initialize result for(let i = 0 ; i < n - 2; i++) { for(let j = i + 1; j < n - 1; j++) { if(arr[i] > arr[j]) { for(let k = j + 1; k < n; k++) { if(arr[j] > arr[k]) invcount++; } } } } return invcount; } // driver program to test above function let arr = [8, 4, 2, 1]; let n = arr.length; document.write("Inversion count : " + getInvCount(arr, n)); // This code is contributed by rag2127 </script>
Inversion Count : 4
Complejidad temporal: O(n^3)
Espacio auxiliar: O(1).
Mejor enfoque:
Podemos reducir la complejidad si consideramos cada elemento arr[i] como elemento medio de inversión, encontramos todos los números mayores que a[i] cuyo índice es menor que i, encontramos todos los números que son menores que a[i] y el índice es mayor que i. Multiplicamos el número de elementos mayores que a[i] por el número de elementos menores que a[i] y lo sumamos al resultado.
A continuación se muestra la implementación de la idea.
C++
// A O(n^2) C++ program to count inversions of size 3 #include<bits/stdc++.h> using namespace std; // Returns count of inversions of size 3 int getInvCount(int arr[], int n) { int invcount = 0; // Initialize result for (int i=1; i<n-1; i++) { // Count all smaller elements on right of arr[i] int small = 0; for (int j=i+1; j<n; j++) if (arr[i] > arr[j]) small++; // Count all greater elements on left of arr[i] int great = 0; for (int j=i-1; j>=0; j--) if (arr[i] < arr[j]) great++; // Update inversion count by adding all inversions // that have arr[i] as middle of three elements invcount += great*small; } return invcount; } // Driver program to test above function int main() { int arr[] = {8, 4, 2, 1}; int n = sizeof(arr)/sizeof(arr[0]); cout << "Inversion Count : " << getInvCount(arr, n); return 0; }
Java
// A O(n^2) Java program to count inversions of size 3 class Inversion { // returns count of inversion of size 3 int getInvCount(int arr[], int n) { int invcount = 0; // initialize result for (int i=0 ; i< n-1; i++) { // count all smaller elements on right of arr[i] int small=0; for (int j=i+1; j<n; j++) if (arr[i] > arr[j]) small++; // count all greater elements on left of arr[i] int great = 0; for (int j=i-1; j>=0; j--) if (arr[i] < arr[j]) great++; // update inversion count by adding all inversions // that have arr[i] as middle of three elements invcount += great*small; } return invcount; } // driver program to test above function public static void main(String args[]) { Inversion inversion = new Inversion(); int arr[] = new int[] {8, 4, 2, 1}; int n = arr.length; System.out.print("Inversion count : " + inversion.getInvCount(arr, n)); } } // This code has been contributed by Mayank Jaiswal
Python3
# A O(n^2) Python3 program to # count inversions of size 3 # Returns count of inversions # of size 3 def getInvCount(arr, n): # Initialize result invcount = 0 for i in range(1,n-1): # Count all smaller elements # on right of arr[i] small = 0 for j in range(i+1 ,n): if (arr[i] > arr[j]): small+=1 # Count all greater elements # on left of arr[i] great = 0; for j in range(i-1,-1,-1): if (arr[i] < arr[j]): great+=1 # Update inversion count by # adding all inversions that # have arr[i] as middle of # three elements invcount += great * small return invcount # Driver program to test above function arr = [8, 4, 2, 1] n = len(arr) print("Inversion Count :",getInvCount(arr, n)) # This code is Contributed by Smitha Dinesh Semwal
C#
// A O(n^2) Java program to count inversions // of size 3 using System; public class Inversion { // returns count of inversion of size 3 static int getInvCount(int []arr, int n) { int invcount = 0; // initialize result for (int i = 0 ; i < n-1; i++) { // count all smaller elements on // right of arr[i] int small = 0; for (int j = i+1; j < n; j++) if (arr[i] > arr[j]) small++; // count all greater elements on // left of arr[i] int great = 0; for (int j = i-1; j >= 0; j--) if (arr[i] < arr[j]) great++; // update inversion count by // adding all inversions that // have arr[i] as middle of // three elements invcount += great * small; } return invcount; } // driver program to test above function public static void Main() { int []arr = new int[] {8, 4, 2, 1}; int n = arr.Length; Console.WriteLine("Inversion count : " + getInvCount(arr, n)); } } // This code has been contributed by anuj_67.
PHP
<?php // A O(n^2) PHP program to count // inversions of size 3 // Returns count of // inversions of size 3 function getInvCount($arr, $n) { // Initialize result $invcount = 0; for ($i = 1; $i < $n - 1; $i++) { // Count all smaller elements // on right of arr[i] $small = 0; for ($j = $i + 1; $j < $n; $j++) if ($arr[$i] > $arr[$j]) $small++; // Count all greater elements // on left of arr[i] $great = 0; for ($j = $i - 1; $j >= 0; $j--) if ($arr[$i] < $arr[$j]) $great++; // Update inversion count by // adding all inversions that // have arr[i] as middle of // three elements $invcount += $great * $small; } return $invcount; } // Driver Code $arr = array (8, 4, 2, 1); $n = sizeof($arr); echo "Inversion Count : " , getInvCount($arr, $n); // This code is contributed by m_kit ?>
Javascript
<script> // A O(n^2) Javascript program to count inversions of size 3 // returns count of inversion of size 3 function getInvCount(arr, n) { let invcount = 0; // initialize result for (let i = 0 ; i < n - 1; i++) { // count all smaller elements on right of arr[i] let small = 0; for (let j = i + 1; j < n; j++) if (arr[i] > arr[j]) small++; // count all greater elements on left of arr[i] let great = 0; for (let j = i - 1; j >= 0; j--) if (arr[i] < arr[j]) great++; // update inversion count by adding all inversions // that have arr[i] as middle of three elements invcount += great*small; } return invcount; } // driver program to test above function let arr=[8, 4, 2, 1]; let n = arr.length; document.write("Inversion count : " +getInvCount(arr, n)); // This code is contributed by avanitrachhadiya2155 </script>
Inversion Count : 4
Complejidad de Tiempo: O(n^2)
Espacio Auxiliar: O(1).
Enfoque de árbol indexado binario:
Al igual que las inversiones de tamaño 2, podemos usar el árbol indexado binario para encontrar inversiones de tamaño 3. Se recomienda encarecidamente consultar primero el artículo a continuación.
Contar inversiones de tamaño dos Usando BIT
La idea es similar al método anterior. Contamos el número de elementos mayores y elementos menores para todos los elementos y luego multiplicamos mayor[] por menor[] y lo sumamos al resultado.
Solución :
- Para averiguar el número de elementos más pequeños para un índice iteramos de n-1 a 0. Para cada elemento a[i] calculamos la función getSum() para (a[i]-1) que da el número de elementos hasta a[i]-1.
- Para averiguar el número de elementos mayores para un índice, iteramos de 0 a n-1. Para cada elemento a[i] calculamos la suma de números hasta a[i] (suma menor o igual a a[i]) por getSum() y lo restamos de i (ya que i es el número total de elementos hasta ese punto ) para que podamos obtener un número de elementos mayor que a[i].
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA