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: haga un bucle para todos los valores posibles de i, j y k y compruebe 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; }
Producción:
Inversion Count : 4
La complejidad temporal de este enfoque es: O (n ^ 3)
Mejor enfoque:
podemos reducir la complejidad si consideramos cada elemento arr [i] como elemento medio de inversión, encuentre todos los números mayores que a [i] cuyo índice es menor que i, encuentra 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; }
Producción :
Inversion Count : 4
Complejidad temporal de este enfoque: O (n ^ 2)
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].
¡ Consulte el artículo completo sobre inversiones de conteo de tamaño tres en una array dada para obtener más detalles!
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