Dată o matrice O de mărime NxN trebuie să găsim numărul de perechi de inversare din el. Numărul de inversiuni într-o matrice este definit ca numărul de perechi care îndeplinesc următoarele condiții:
- x1? x2
- şi1? şi2
- Topor2][şi2]< A[x1][şi1]
Constrângeri:
- 1 ? Oij? 109
- 1 ? N ? 103
Exemple:
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 Pentru a rezolva această problemă trebuie să știm următoarele lucruri:
- Găsirea numărului de perechi de inversare într-o matrice 1D utilizând arborele indexat binar (BIT) https://www.geeksforgeeks.org/dsa/inversion-count-in-array-using-bit/
- 2D BIT https://www.geeksforgeeks.org/dsa/two-dimensional-binary-indexed-tree-or-fenwick-tree/
Deoarece trebuie să găsim numărul de perechi de inversare într-o matrice, primul lucru pe care trebuie să-l facem este să stocăm elementele matricei într-o altă matrice, să spunem v și să sortăm matricea v, astfel încât să putem compara elementele matricei nesortate cu v și să găsim numărul de perechi de inversare folosind BIT. Dar este dat că valorile elementelor sunt foarte mari (109) deci nu putem folosi valorile elementelor din matrice ca indici în BIT. Astfel, trebuie să folosim poziția elementelor ca indici în BIT-ul 2D.
Vom folosi tuplu (-A[i][j] i j) pentru fiecare element al matricei și îl vom stoca într-o matrice, spun „v”. Apoi trebuie să sortăm v în funcție de valoarea lui -A[i][j] în ordine crescătoare, astfel încât cel mai mare element al matricei să fie stocat la indicele 0 și cel mai mic la ultimul indice al lui v. Acum problema se reduce la găsirea perechilor de inversare într-un tablou 1D, singura excepție este că vom folosi un BIT 2D.
Rețineți că aici folosim valori negative ale lui A[i][j] pur și simplu pentru că vom parcurge v de la stânga la dreapta, adică de la cel mai mare număr din matrice la cel mai mic (pentru că asta facem când găsim perechi de inversare într-o matrice 1D folosind BIT). Se pot folosi, de asemenea, valori pozitive și să traverseze v de la dreapta la stânga, rezultatul final va rămâne același.
Algoritm:
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.
Implementare:
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
Ieșire
The number of inversion pairs are : 43
Complexitatea timpului : O(log(NxN)) unde N este dimensiunea matricei
Complexitatea spațială : O(NxN)
Creați un test