Givet en matrix EN af størrelse NxN vi skal finde antallet af inversionspar i den. Inversionstal i en matrix er defineret som antallet af par, der opfylder følgende betingelser:
- x1? x2
- og1? og2
- Økse2][og2]< A[x1][og1]
Begrænsninger:
- 1 ? ENij? 109
- 1 ? N ? 103
Eksempler:
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 For at løse dette problem skal vi vide følgende ting:
- Find antallet af inversionspar i et 1D-array ved hjælp af Binary Indexed Tree (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/
Da vi skal finde antallet af inversionspar i en matrix, er det første, vi skal gøre, at gemme elementerne i matrixen i et andet array, sige v og sortere arrayet v, så vi kan sammenligne elementerne i den usorterede matrix med v og finde antallet af inversionspar ved hjælp af BIT. Men det er givet, at værdierne af elementerne er meget store (109) så vi kan ikke bruge værdierne af elementerne i matricen som indeks i BIT. Derfor skal vi bruge elementernes position som indekser i 2D BIT.
Vi skal bruge tuple (-A[i][j] i j) for hvert element i matrixen og gemme det i en matrix og sige 'v'. Så skal vi sortere v efter værdien af -A[i][j] i stigende rækkefølge, så det største element i matricen vil blive lagret ved indeks 0 og det mindste ved det sidste indeks af v. Nu er problemet reduceret til at finde inversionspar i et 1D-array, den eneste undtagelse er, at vi skal bruge en 2D BIT.
Bemærk, at vi her bruger negative værdier af A[i][j] simpelthen fordi vi skal krydse v fra venstre mod højre, dvs. fra det største tal i matricen til det mindste (fordi det er det, vi gør, når vi finder inversionspar i et 1D-array ved hjælp af BIT). Man kan også bruge positive værdier og krydse v fra højre til venstre. Det endelige resultat forbliver det samme.
Algoritme:
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.
Implementering:
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
Produktion
The number of inversion pairs are : 43
Tidskompleksitet : O(log(NxN)) hvor N er størrelsen af matrixen
Rumkompleksitet : O(NxN)
Opret quiz