Étant donné une matrice UN de taille NxN nous devons y trouver le nombre de paires d’inversions. Le nombre d'inversions dans une matrice est défini comme le nombre de paires satisfaisant les conditions suivantes :
- x1? x2
- et1? et2
- Hache2][et2]< A[x1][et1]
Contraintes :
- 1 ? UNje? 109
- 1 ? N ? 103
Exemples :
For simplicity let's take a 2x2 matrix : A = {{7 5} {3 1}}; The inversion pairs are : (7 5) (3 1) (7 3) (5 1) and (7 1) Output : 5 Pour résoudre ce problème, nous devons connaître les choses suivantes :
- Recherche du nombre de paires d'inversion dans un tableau 1D à l'aide de l'arbre indexé binaire (BIT) https://www.geeksforgeeks.org/dsa/inversion-count-in-array-using-bit/
- BITS 2D https://www.geeksforgeeks.org/dsa/two-dimensionnel-binary-indexed-tree-or-fenwick-tree/
Puisque nous devons trouver le nombre de paires d'inversion dans une matrice, la première chose que nous devons faire est de stocker les éléments de la matrice dans un autre tableau, disons v et trier le tableau v afin que nous puissions comparer les éléments de la matrice non triée avec v et trouver le nombre de paires d'inversion en utilisant BIT. Mais on sait que les valeurs des éléments sont très grandes (109) nous ne pouvons donc pas utiliser les valeurs des éléments de la matrice comme indices dans le BIT. Nous devons donc utiliser la position des éléments comme index dans le BIT 2D.
Nous allons utiliser le tuple (-A[i][j] i j) pour chaque élément de la matrice et le stocker dans un tableau, disons 'v'. Ensuite, nous devons trier v en fonction de la valeur de -A[i][j] par ordre croissant afin que le plus grand élément de la matrice soit stocké à l'index 0 et le plus petit au dernier index de v. Maintenant, le problème se réduit à trouver des paires d'inversion dans un tableau 1D, la seule exception est que nous allons utiliser un BIT 2D.
Notez qu'ici nous utilisons des valeurs négatives de A[i][j] simplement parce que nous allons parcourir v de gauche à droite, c'est-à-dire du plus grand nombre de la matrice au plus petit (car c'est ce que nous faisons lorsque nous trouvons des paires d'inversion dans un tableau 1D à l'aide de BIT). On peut également utiliser des valeurs positives et parcourir v de droite à gauche pour que le résultat final reste le même.
Algorithme :
1. Initialize inv_pair_cnt = 0 which will store the number of inversion pairs. 2. Store the tuple (-A[i][j] i j) in an array say v where A[i][j] is the element of the matrix A at position (i j). 3. Sort the array v according to the first element of the tuple i.e. according to the value of -A[i][j]. 4. Traverse the array v and do the following : - Initialize an array say 'pairs' to store the position (i j) of the tuples of v. - while the current tuple of v and all its adjacent tuples whose first value i.e. -A[i][j] is same do - Push the current tuple's position pair (i j) into 'pairs'. - Add to inv_pair_cnt the number of elements which are less than the current element(i.e. A[i][j]) and lie on the right side in the sorted array v by calling the query operation of BIT and passing i and j as arguments. - For each position pair (i j) stored in the array 'pairs' update the position (i j) in the 2D BIT by 1. 5. Finally inv_pair_cnt will contain the number of inversion pairs.
Mise en œuvre:
C++// C++ program to count the number of inversion // pairs in a 2D matrix #include
# Python3 program to count the number of inversion # pairs in a 2D matrix # for simplicity we are taking N as 4 N = 4 # Function to update a 2D BIT. It updates the # value of bit[l][r] by adding val to bit[l][r] def update(l r val bit): i = l while(i <= N): j = r while(j <= N): bit[i][j] += val j += j & -j i += i & -i # function to find cumulative sum upto # index (l r) in the 2D BIT def query(l r bit): ret = 0 i = l while(i > 0): j = r while(j > 0): ret += bit[i][j] j -= j & -j i -= i & -i return ret # function to count and return the number # of inversion pairs in the matrix def countInversionPairs(mat): # the 2D bit array and initialize it with 0. bit = [[0 for i in range(N + 1)] for j in range(N + 1)] # v will store the tuple (-mat[i][j] i j) v = [] # store the tuples in the vector v for i in range(N): for j in range(N): # Note that we are not using the pair # (0 0) because BIT update and query # operations are not done on index 0 v.append([-mat[i][j] [i + 1 j + 1]]) # sort the vector v according to the # first element of the tuple i.e. -mat[i][j] v.sort() # inv_pair_cnt will store the number of # inversion pairs inv_pair_cnt = 0 # traverse all the tuples of vector v i = 0 while (i < len(v)): curr = i # 'pairs' will store the position of each element # i.e. the pair (i j) of each tuple of the vector v pairs = [] # consider the current tuple in v and all its # adjacent tuples whose first value i.e. the # value of –mat[i][j] is same while (curr < len(v) and (v[curr][0] == v[i][0])): # push the position of the current element in 'pairs' pairs.append([v[curr][1][0] v[curr][1][1]]) # add the number of elements which are # less than the current element and lie on the right # side in the vector v inv_pair_cnt += query(v[curr][1][0] v[curr][1][1] bit) curr += 1 # traverse the 'pairs' vector for it in pairs: x = it[0] y = it[1] # update the position (x y) by 1 update(x y 1 bit) i = curr return inv_pair_cnt # Driver code mat = [[4 7 2 9 ][ 6 4 1 7 ] [ 5 3 8 1 ][3 2 5 6]] inv_pair_cnt = countInversionPairs(mat) print('The number of inversion pairs are :' inv_pair_cnt) # This code is contributed by shubhamsingh10
// C# program to count the number of inversion // Tuples in a 2D matrix using System; using System.Collections.Generic; class GFG { // for simplicity we are taking N as 4 static int N = 4; // Function to update a 2D BIT. It updates the // value of bit[l r] by adding val to bit[l r] static void update(int l int r int val int[] bit) { for (int x = l; x <= N; x += (x & -x)) for (int j = r; j <= N; j += j & -j) bit[x j] += val; } // function to find cumulative sum upto // index (l r) in the 2D BIT static int query(int l int r int[] bit) { int ret = 0; for (int x = l; x > 0; x -= (x & -x)) for (int j = r; j > 0; j -= (j & -j)) ret += bit[x j]; return ret; } // function to count and return the number // of inversion Tuples in the matrix static int countInversionTuples(int[] mat) { // the 2D bit array and initialize it with 0. int[ ] bit = new int[N + 1 N +1]; for (int x = 0; x <= N; x++) for (int y = 0; y <= N; y++) bit[x y] = 0; // v will store the tuple (-mat[i j] i j) List<Tuple<int Tuple<int int> > > v = new List<Tuple<int Tuple<int int> > >(); // store the tuples in the vector v for (int x = 0; x < N; ++x) for (int j = 0; j < N; ++j) // Note that we are not using the Tuple // (0 0) because BIT update and query // operations are not done on index 0 v.Add(Tuple.Create(-mat[x j] Tuple.Create(x+1 j+1))); // sort the vector v according to the // first element of the tuple i.e. -mat[i j] v.Sort(); // inv_Tuple_cnt will store the number of // inversion Tuples int inv_Tuple_cnt = 0; // traverse all the tuples of vector v int i = 0; while (i < v.Count) { int curr = i; // 'Tuples' will store the position of each element // i.e. the Tuple (i j) of each tuple of the vector v List<Tuple<int int>> Tuples = new List<Tuple<int int>>(); // consider the current tuple in v and all its // adjacent tuples whose first value i.e. the // value of –mat[i j] is same while (curr < v.Count && (v[curr].Item1 == v[i].Item1)) { // push the position of the current element in 'Tuples' Tuples.Add(Tuple.Create(v[curr].Item2.Item1 v[curr].Item2.Item2)); // add the number of elements which are // less than the current element and lie on the right // side in the vector v inv_Tuple_cnt += query(v[curr].Item2.Item1 v[curr].Item2.Item2 bit); curr++; } // traverse the 'Tuples' vector foreach (var it in Tuples) { int x = it.Item1; int y = it.Item2; // update the position (x y) by 1 update(x y 1 bit); } i = curr; } return inv_Tuple_cnt; } // Driver program public static void Main(string[] args) { int[ ] mat = { { 4 7 2 9 } { 6 4 1 7 } { 5 3 8 1 } { 3 2 5 6 } }; int inv_Tuple_cnt = countInversionTuples(mat); Console.WriteLine( 'The number of inversion Tuples are : ' + inv_Tuple_cnt); } } // This code is contributed by phasing17.
// JavaScript program to count the number of inversion // pairs in a 2D matrix // for simplicity we are taking N as 4 let N = 4 // Function to update a 2D BIT. It updates the // value of bit[l][r] by adding val to bit[l][r] function update(l r val bit) { let i = l while(i <= N) { let j = r while(j <= N) { bit[i][j] += val j += (j & -j) } i += (i & -i) } return bit } // function to find cumulative sum upto // index (l r) in the 2D BIT function query(l r bit) { let ret = 0 let i = l while(i > 0) { let j = r while(j > 0) { ret += bit[i][j] j -= (j & -j) } i -= (i & -i) } return ret } // function to count and return the number // of inversion pairs in the matrix function countInversionPairs(mat) { // the 2D bit array and initialize it with 0. let bit = new Array(N + 1) for (let i = 0; i <= N; i++) bit[i] = new Array(N + 1).fill(0) // v will store the tuple (-mat[i][j] i j) let v = [] // store the tuples in the vector v for (let i = 0; i < N; i++) for (var j = 0; j < N; j++) // Note that we are not using the pair // (0 0) because BIT update and query // operations are not done on index 0 v.push([-mat[i][j] [i + 1 j + 1]]) // sort the vector v according to the // first element of the tuple i.e. -mat[i][j] v.sort(function(a b) { return a[0] - b[0]}) // inv_pair_cnt will store the number of // inversion pairs let inv_pair_cnt = 0 // traverse all the tuples of vector v let i = 0 while (i < v.length) { let curr = i // 'pairs' will store the position of each element // i.e. the pair (i j) of each tuple of the vector v let pairs = [] // consider the current tuple in v and all its // adjacent tuples whose first value i.e. the // value of –mat[i][j] is same while (curr < v.length && (v[curr][0] == v[i][0])) { // push the position of the current element in 'pairs' pairs.push([v[curr][1][0] v[curr][1][1]]) // add the number of elements which are // less than the current element and lie on the right // side in the vector v inv_pair_cnt += query(v[curr][1][0] v[curr][1][1] bit) curr += 1 } // traverse the 'pairs' vector for (let it of pairs) { let x = it[0] let y = it[1] // update the position (x y) by 1 bit = update(x y 1 bit) } i = curr } return inv_pair_cnt } // Driver code let mat = [[4 7 2 9 ][ 6 4 1 7 ] [ 5 3 8 1 ][3 2 5 6]] let inv_pair_cnt = countInversionPairs(mat) console.log('The number of inversion pairs are ' inv_pair_cnt) // This code is contributed by phasing17
import java.util.*; class Main { static final int N = 4; static void update(int l int r int val int[][] bit) { for (int i = l; i <= N; i += i & -i) for (int j = r; j <= N; j += j & -j) bit[i][j] += val; } static long query(int l int r int[][] bit) { long ret = 0; for (int i = l; i > 0; i -= i & -i) for (int j = r; j > 0; j -= j & -j) ret += bit[i][j]; return ret; } static long countInversionPairs(int[][] mat) { int[][] bit = new int[N + 1][N + 1]; List<AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>>> v = new ArrayList<>(); for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) v.add(new AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>>(-mat[i][j] new AbstractMap.SimpleEntry<Integer Integer>(i + 1 j + 1))); Collections.sort(v new Comparator<AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>>>() { @Override public int compare(AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>> a AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>> b) { return a.getKey().compareTo(b.getKey()); } }); long invPairCnt = 0; int i = 0; while (i < v.size()) { int curr = i; List<AbstractMap.SimpleEntry<Integer Integer>> pairs = new ArrayList<>(); while (curr < v.size() && (v.get(curr).getKey().equals(v.get(i).getKey()))) { pairs.add(v.get(curr).getValue()); invPairCnt += query(v.get(curr).getValue().getKey() v.get(curr).getValue().getValue() bit); curr++; } for (AbstractMap.SimpleEntry<Integer Integer> p : pairs) { int x = p.getKey(); int y = p.getValue(); update(x y 1 bit); } i = curr; } return invPairCnt; } public static void main(String[] args) { int[][] mat = {{4 7 2 9} {6 4 1 7} {5 3 8 1} {3 2 5 6}}; long invPairCnt = countInversionPairs(mat); System.out.println('The number of inversion pairs are: ' + invPairCnt); } } // This code is contributed by Prince Kumar
Sortir
The number of inversion pairs are : 43
Complexité temporelle : O(log(NxN)) où N est la taille de la matrice
Complexité spatiale : O(NxN)
Créer un quiz