Dada una array de n enteros distintos y un entero k. Averigüe el número de subsecuencias de tal que , y . En otras palabras, genera el número total de inversiones de longitud k.
Ejemplos:
Input : a[] = {9, 3, 6, 2, 1}, k = 3 Output : 7 The seven inversions are {9, 3, 2}, {9, 3, 1}, {9, 6, 2}, {9, 6, 1}, {9, 2, 1}, {3, 2, 1} and {6, 2, 1}. Input : a[] = {5, 6, 4, 9, 2, 7, 1}, k = 4 Output : 2 The two inversions are {5, 4, 2, 1}, {6, 4, 2, 1}.
Ya hemos discutido la inversión de conteo de longitud tres aquí . Esta publicación generalizará el enfoque utilizando el árbol indexado binario y las inversiones de conteo utilizando BIT . Puede encontrar más información sobre los árboles indexados binarios en el artículo real que Peter M. Fenwick publicó, aquí .
1. Para empezar, primero convertimos la array dada en una permutación de elementos (Tenga en cuenta que esto siempre es posible ya que los elementos son distintos).
2. El enfoque es mantener un conjunto de árboles k Fenwick. Que se denote por donde , realiza un seguimiento del número de subsecuencias de longitud que comienzan con .
3. Iteramos desde el final de la array convertida hasta el principio. Para cada elemento de array convertido , actualizamos el conjunto de árboles de Fenwick, como: Para cada , cada subsecuencia de longitud que comienza con un número menor que también forma parte de secuencias de longitud .
El resultado final se obtiene mediante la suma de las ocurrencias de .
La implementación se analiza a continuación:
C++
// C++ program to count inversions of size k using // Binary Indexed Tree #include <bits/stdc++.h> using namespace std; // It is beneficial to declare the 2D BIT globally // since passing it into functions will create // additional overhead const int K = 51; const int N = 100005; int BIT[K][N] = { 0 }; // update function. "t" denotes the t'th Binary // indexed tree void updateBIT(int t, int i, int val, int n) { // Traversing the t'th BIT while (i <= n) { BIT[t][i] = BIT[t][i] + val; i = i + (i & (-i)); } } // function to get the sum. // "t" denotes the t'th Binary indexed tree int getSum(int t, int i) { int res = 0; // Traversing the t'th BIT while (i > 0) { res = res + BIT[t][i]; i = i - (i & (-i)); } return res; } // Converts an array to an array with values from 1 to n // and relative order of smaller and greater elements // remains same. For example, {7, -90, 100, 1} is // converted to {3, 1, 4, 2 } void convert(int arr[], int n) { // Create a copy of arr[] in temp and sort // the temp array in increasing order int temp[n]; for (int i = 0; i < n; i++) temp[i] = arr[i]; sort(temp, temp + n); // Traverse all array elements for (int i = 0; i < n; i++) { // lower_bound() Returns pointer to the // first element greater than or equal // to arr[i] arr[i] = lower_bound(temp, temp + n, arr[i]) - temp + 1; } } // Returns count of inversions of size three int getInvCount(int arr[], int n, int k) { // Convert arr[] to an array with values from // 1 to n and relative order of smaller and // greater elements remains same. For example, // {7, -90, 100, 1} is converted to {3, 1, 4, 2 } convert(arr, n); // iterating over the converted array in // reverse order. for (int i = n - 1; i >= 0; i--) { int x = arr[i]; // update the BIT for l = 1 updateBIT(1, x, 1, n); // update BIT for all other BITs for (int l = 1; l < k; l++) { updateBIT(l + 1, x, getSum(l, x - 1), n); } } // final result return getSum(k, n); } // Driver program to test above function int main() { int arr[] = { 5, 6, 4, 9, 3, 7, 2, 1 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 4; cout << "Inversion Count : " << getInvCount(arr, n, k); return 0; }
Java
// Java program to count // inversions of size k using // Binary Indexed Tree import java.io.*; import java.util.Arrays; import java.util.ArrayList; import java.lang.*; import java.util.Collections; class GFG { // It is beneficial to declare // the 2D BIT globally since // passing it into functions // will create additional overhead static int K = 51; static int N = 100005; static int BIT[][] = new int[K][N]; // update function. "t" denotes // the t'th Binary indexed tree static void updateBIT(int t, int i, int val, int n) { // Traversing the t'th BIT while (i <= n) { BIT[t][i] = BIT[t][i] + val; i = i + (i & (-i)); } } // function to get the sum. // "t" denotes the t'th // Binary indexed tree static int getSum(int t, int i) { int res = 0; // Traversing the t'th BIT while (i > 0) { res = res + BIT[t][i]; i = i - (i & (-i)); } return res; } // Converts an array to an // array with values from // 1 to n and relative order // of smaller and greater // elements remains same. // For example, {7, -90, 100, 1} // is converted to {3, 1, 4, 2 } static void convert(int arr[], int n) { // Create a copy of arr[] in // temp and sort the temp // array in increasing order int temp[] = new int[n]; for (int i = 0; i < n; i++) temp[i] = arr[i]; Arrays.sort(temp); // Traverse all array elements for (int i = 0; i < n; i++) { // lower_bound() Returns // pointer to the first // element greater than // or equal to arr[i] arr[i] = Arrays.binarySearch(temp, arr[i]) + 1; } } // Returns count of inversions // of size three static int getInvCount(int arr[], int n, int k) { // Convert arr[] to an array // with values from 1 to n and // relative order of smaller // and greater elements remains // same. For example, {7, -90, 100, 1} // is converted to {3, 1, 4, 2 } convert(arr, n); // iterating over the converted // array in reverse order. for (int i = n - 1; i >= 0; i--) { int x = arr[i]; // update the BIT for l = 1 updateBIT(1, x, 1, n); // update BIT for all other BITs for (int l = 1; l < k; l++) { updateBIT(l + 1, x, getSum(l, x - 1), n); } } // final result return getSum(k, n); } // Driver Code public static void main(String[] args) { int arr[] = { 5, 6, 4, 9, 3, 7, 2, 1 }; int n = arr.length; int k = 4; System.out.println("Inversion Count : " + getInvCount(arr, n, k)); } }
Python3
# Python3 program to count inversions # of size k using Binary Indexed Tree # It is beneficial to declare the 2D BIT # globally since passing it o functions # will create additional overhead K = 51 N = 100005 BIT = [[0 for x in range(N)] for y in range(K)] # update function. "t" denotes # the t'th Binary indexed tree def updateBIT(t, i, val, n): # Traversing the t'th BIT while (i <= n): BIT[t][i] = BIT[t][i] + val i = i + (i & (-i)) # function to get the sum. "t" denotes # the t'th Binary indexed tree def getSum(t, i): res = 0 # Traversing the t'th BIT while (i > 0): res = res + BIT[t][i] i = i - (i & (-i)) return res # Converts an array to an array with # values from 1 to n and relative order # of smaller and greater elements remains # same. For example, 7, -90, 100, 1 is # converted to 3, 1, 4, 2 def convert( arr, n): # Create a copy of arr[] in temp and sort # the temp array in increasing order temp = [0] * n for i in range(n): temp[i] = arr[i] temp = sorted(temp) j = 1 for i in temp: arr[arr.index(i)] = j j += 1 # Returns count of inversions # of size three def getInvCount(arr, n, k) : # Convert arr[] to an array with # values from 1 to n and relative # order of smaller and greater elements # remains same. For example, 7, -90, 100, 1 # is converted to 3, 1, 4, 2 convert(arr, n) # iterating over the converted array # in reverse order. for i in range(n - 1, -1, -1): x = arr[i] # update the BIT for l = 1 updateBIT(1, x, 1, n) # update BIT for all other BITs for l in range(1, k): updateBIT(l + 1, x, getSum(l, x - 1), n) # final result return getSum(k, n) # Driver code if __name__ =="__main__": arr = [5, 6, 4, 9, 3, 7, 2, 1] n = 8 k = 4 print("Inversion Count :", getInvCount(arr, n, k)) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to count // inversions of size k using // Binary Indexed Tree using System; using System.Linq; class GFG { // It is beneficial to declare // the 2D BIT globally since // passing it into functions // will create additional overhead static int K = 51; static int N = 100005; static int [,]BIT = new int[K, N]; // update function. "t" denotes // the t'th Binary indexed tree static void updateBIT(int t, int i, int val, int n) { // Traversing the t'th BIT while (i <= n) { BIT[t, i] = BIT[t, i] + val; i = i + (i & (-i)); } } // function to get the sum. // "t" denotes the t'th // Binary indexed tree static int getSum(int t, int i) { int res = 0; // Traversing the t'th BIT while (i > 0) { res = res + BIT[t, i]; i = i - (i & (-i)); } return res; } // Converts an array to an // array with values from // 1 to n and relative order // of smaller and greater // elements remains same. // For example, {7, -90, 100, 1} // is converted to {3, 1, 4, 2 } static void convert(int []arr, int n) { // Create a copy of arr[] in // temp and sort the temp // array in increasing order int []temp = new int[n]; for (int i = 0; i < n; i++) temp[i] = arr[i]; Array.Sort(temp); // Traverse all array elements for (int i = 0; i < n; i++) { // lower_bound() Returns // pointer to the first // element greater than // or equal to arr[i] arr[i] = Array.BinarySearch(temp, arr[i]) + 1; } } // Returns count of inversions // of size three static int getInvCount(int []arr, int n, int k) { // Convert arr[] to an array // with values from 1 to n and // relative order of smaller // and greater elements remains // same. For example, {7, -90, 100, 1} // is converted to {3, 1, 4, 2 } convert(arr, n); // iterating over the converted // array in reverse order. for (int i = n - 1; i >= 0; i--) { int x = arr[i]; // update the BIT for l = 1 updateBIT(1, x, 1, n); // update BIT for all other BITs for (int l = 1; l < k; l++) { updateBIT(l + 1, x, getSum(l, x - 1), n); } } // final result return getSum(k, n); } // Driver Code public static void Main(String[] args) { int []arr = { 5, 6, 4, 9, 3, 7, 2, 1 }; int n = arr.Length; int k = 4; Console.WriteLine("Inversion Count : " + getInvCount(arr, n, k)); } } // This code is contributed by PrinciRaj1992
Producción:
Inversion Count : 11
Tiempo Complejidad
Espacio Auxiliar
Cabe señalar que este no es el único enfoque para resolver el problema de encontrar k-inversiones. Obviamente, cualquier problema que se pueda resolver con BIT también se puede resolver con Segment Tree. Además, podemos usar un algoritmo basado en Merge-Sort y también una estructura de datos basada en políticas de C++. Además, a expensas de una mayor complejidad de tiempo, también se puede utilizar el enfoque de programación dinámica.
Publicación traducida automáticamente
Artículo escrito por AayushChaturvedi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA