Dada una array arr[] , la tarea es encontrar el recuento total de inversiones significativas para la array. Dos elementos arr[i] y arr[j] forman una inversión significativa si arr[i] > 2 * arr[j] e i < j .
Ejemplos:
Entrada: arr[] = { 1, 20, 6, 4, 5 }
Salida: 3
Los pares de inversión significativos son (20, 6), (20, 5) y (20, 4).
Entrada: arr[] = { 1, 20 }
Salida: 0
Prerrequisito: Método de inversiones de conteo :
- La idea básica para encontrar inversiones se basará en el requisito previo anterior, utilizando el enfoque Divide and Conquer del tipo de fusión modificado .
- Se puede contar el número de inversiones significativas en la mitad izquierda y la mitad derecha. Incluir el conteo de inversión significativa con índice (i, j) tal que i esté en la mitad izquierda y j esté en la mitad derecha y luego sume los tres para obtener el conteo total de inversión significativa.
- El enfoque utilizado en el enlace anterior se puede modificar para realizar dos pases de la mitad izquierda y derecha durante el paso de fusión. En el primer paso, calcule el número de inversiones significativas en la array fusionada. Para cualquier índice i en la array izquierda si arr[i] > 2 * arr[j], entonces todos los elementos a la izquierda del i-ésimo índice en la array izquierda también contribuirán a un recuento de inversión significativo. Incremento j. De lo contrario incrementa i.
- El segundo paso será construir la array fusionada. Aquí se requieren dos pases porque en el conteo de inversión normal, los dos pases moverían i y j en los mismos puntos, por lo que se pueden combinar, pero eso no es cierto en este caso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; int _mergeSort(int arr[], int temp[], int left, int right); int merge(int arr[], int temp[], int left, int mid, int right); // Function that sorts the input array // and returns the number of inversions // in the array int mergeSort(int arr[], int array_size) { int temp[array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } // Recursive function that sorts the input // array and returns the number of // inversions in the array int _mergeSort(int arr[], int temp[], int left, int right) { int mid, inv_count = 0; if (right > left) { // Divide the array into two parts and // call _mergeSortAndCountInv() // for each of the parts mid = (right + left) / 2; // Inversion count will be sum of the // inversions in the left-part, the right-part // and the number of inversions in merging inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); // Merge the two parts inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } // Function that merges the two sorted arrays // and returns the inversion count in the arrays int merge(int arr[], int temp[], int left, int mid, int right) { int i, j, k; int inv_count = 0; // i is the index for the left subarray i = left; // j is the index for the right subarray j = mid; // k is the index for the resultant // merged subarray k = left; // First pass to count number // of significant inversions while ((i <= mid - 1) && (j <= right)) { if (arr[i] > 2 * arr[j]) { inv_count += (mid - i); j++; } else { i++; } } // i is the index for the left subarray i = left; // j is the index for the right subarray j = mid; // k is the index for the resultant // merged subarray k = left; // Second pass to merge the two sorted arrays while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // Copy the remaining elements of the left // subarray (if there are any) to temp while (i <= mid - 1) temp[k++] = arr[i++]; // Copy the remaining elements of the right // subarray (if there are any) to temp while (j <= right) temp[k++] = arr[j++]; // Copy back the merged elements to // the original array for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } // Driver code int main() { int arr[] = { 1, 20, 6, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout << mergeSort(arr, n); return 0; }
Java
// Java implementation of the above approach class GFG { // Function that sorts the input array // and returns the number of inversions // in the array static int mergeSort(int arr[], int array_size) { int temp[] = new int[array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } // Recursive function that sorts the input // array and returns the number of // inversions in the array static int _mergeSort(int arr[], int temp[], int left, int right) { int mid, inv_count = 0; if (right > left) { // Divide the array into two parts and // call _mergeSortAndCountInv() // for each of the parts mid = (right + left) / 2; // Inversion count will be sum of the // inversions in the left-part, the right-part // and the number of inversions in merging inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); // Merge the two parts inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } // Function that merges the two sorted arrays // and returns the inversion count in the arrays static int merge(int arr[], int temp[], int left, int mid, int right) { int i, j, k; int inv_count = 0; // i is the index for the left subarray i = left; // j is the index for the right subarray j = mid; // k is the index for the resultant // merged subarray k = left; // First pass to count number // of significant inversions while ((i <= mid - 1) && (j <= right)) { if (arr[i] > 2 * arr[j]) { inv_count += (mid - i); j++; } else { i++; } } // i is the index for the left subarray i = left; // j is the index for the right subarray j = mid; // k is the index for the resultant // merged subarray k = left; // Second pass to merge the two sorted arrays while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // Copy the remaining elements of the left // subarray (if there are any) to temp while (i <= mid - 1) temp[k++] = arr[i++]; // Copy the remaining elements of the right // subarray (if there are any) to temp while (j <= right) temp[k++] = arr[j++]; // Copy back the merged elements to // the original array for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } // Driver code public static void main (String[] args) { int arr[] = { 1, 20, 6, 4, 5 }; int n = arr.length; System.out.println(mergeSort(arr, n)); } } // This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function that sorts the input array # and returns the number of inversions # in the array def mergeSort(arr, array_size): temp = [0 for i in range(array_size)] return _mergeSort(arr, temp, 0, array_size - 1) # Recursive function that sorts the input # array and returns the number of # inversions in the array def _mergeSort(arr, temp, left, right): mid, inv_count = 0, 0 if (right > left): # Divide the array into two parts and # call _mergeSortAndCountInv() # for each of the parts mid = (right + left) // 2 # Inversion count will be sum of the # inversions in the left-part, the right-part # and the number of inversions in merging inv_count = _mergeSort(arr, temp, left, mid) inv_count += _mergeSort(arr, temp, mid + 1, right) # Merge the two parts inv_count += merge(arr, temp, left, mid + 1, right) return inv_count # Function that merges the two sorted arrays # and returns the inversion count in the arrays def merge(arr, temp, left,mid, right): inv_count = 0 # i is the index for the left subarray i = left # j is the index for the right subarray j = mid # k is the index for the resultant # merged subarray k = left # First pass to count number # of significant inversions while ((i <= mid - 1) and (j <= right)): if (arr[i] > 2 * arr[j]): inv_count += (mid - i) j += 1 else: i += 1 # i is the index for the left subarray i = left # j is the index for the right subarray j = mid # k is the index for the resultant # merged subarray k = left # Second pass to merge the two sorted arrays while ((i <= mid - 1) and (j <= right)): if (arr[i] <= arr[j]): temp[k] = arr[i] i, k = i + 1, k + 1 else: temp[k] = arr[j] k, j = k + 1, j + 1 # Copy the remaining elements of the left # subarray (if there are any) to temp while (i <= mid - 1): temp[k] = arr[i] i, k = i + 1, k + 1 # Copy the remaining elements of the right # subarray (if there are any) to temp while (j <= right): temp[k] = arr[j] j, k = j + 1, k + 1 # Copy back the merged elements to # the original array for i in range(left, right + 1): arr[i] = temp[i] return inv_count # Driver code arr = [1, 20, 6, 4, 5] n = len(arr) print(mergeSort(arr, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the above approach using System; class GFG { // Function that sorts the input array // and returns the number of inversions // in the array static int mergeSort(int []arr, int array_size) { int []temp = new int[array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } // Recursive function that sorts the input // array and returns the number of // inversions in the array static int _mergeSort(int []arr, int []temp, int left, int right) { int mid, inv_count = 0; if (right > left) { // Divide the array into two parts and // call _mergeSortAndCountInv() // for each of the parts mid = (right + left) / 2; // Inversion count will be sum of the // inversions in the left-part, the right-part // and the number of inversions in merging inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); // Merge the two parts inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } // Function that merges the two sorted arrays // and returns the inversion count in the arrays static int merge(int []arr, int []temp, int left, int mid, int right) { int i, j, k; int inv_count = 0; // i is the index for the left subarray i = left; // j is the index for the right subarray j = mid; // k is the index for the resultant // merged subarray k = left; // First pass to count number // of significant inversions while ((i <= mid - 1) && (j <= right)) { if (arr[i] > 2 * arr[j]) { inv_count += (mid - i); j++; } else { i++; } } // i is the index for the left subarray i = left; // j is the index for the right subarray j = mid; // k is the index for the resultant // merged subarray k = left; // Second pass to merge the two sorted arrays while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // Copy the remaining elements of the left // subarray (if there are any) to temp while (i <= mid - 1) temp[k++] = arr[i++]; // Copy the remaining elements of the right // subarray (if there are any) to temp while (j <= right) temp[k++] = arr[j++]; // Copy back the merged elements to // the original array for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } // Driver code public static void Main () { int []arr = { 1, 20, 6, 4, 5 }; int n = arr.Length; Console.WriteLine(mergeSort(arr, n)); } } // This code is contributed by anuj_67..
Javascript
<script> // Javascript implementation of the above approach // Function that sorts the input array // and returns the number of inversions // in the array function mergeSort(arr, array_size) { let temp = new Array(array_size); return _mergeSort(arr, temp, 0, array_size - 1); } // Recursive function that sorts the input // array and returns the number of // inversions in the array function _mergeSort(arr, temp, left, right) { let mid, inv_count = 0; if (right > left) { // Divide the array into two parts and // call _mergeSortAndCountInv() // for each of the parts mid = parseInt((right + left) / 2, 10); // Inversion count will be sum of the // inversions in the left-part, the right-part // and the number of inversions in merging inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); // Merge the two parts inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } // Function that merges the two sorted arrays // and returns the inversion count in the arrays function merge(arr, temp, left, mid, right) { let i, j, k; let inv_count = 0; // i is the index for the left subarray i = left; // j is the index for the right subarray j = mid; // k is the index for the resultant // merged subarray k = left; // First pass to count number // of significant inversions while ((i <= mid - 1) && (j <= right)) { if (arr[i] > 2 * arr[j]) { inv_count += (mid - i); j++; } else { i++; } } // i is the index for the left subarray i = left; // j is the index for the right subarray j = mid; // k is the index for the resultant // merged subarray k = left; // Second pass to merge the two sorted arrays while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // Copy the remaining elements of the left // subarray (if there are any) to temp while (i <= mid - 1) temp[k++] = arr[i++]; // Copy the remaining elements of the right // subarray (if there are any) to temp while (j <= right) temp[k++] = arr[j++]; // Copy back the merged elements to // the original array for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } let arr = [ 1, 20, 6, 4, 5 ]; let n = arr.length; document.write(mergeSort(arr, n)); // This code is contributed by mukesh07. </script>
Producción:
3