행렬이 주어지면 에이 크기의 NxN 그 안에 있는 반전 쌍의 수를 찾아야 합니다. 행렬의 반전 횟수는 다음 조건을 만족하는 쌍의 수로 정의됩니다.
- 엑스1? 엑스2
- 그리고1? 그리고2
- 도끼2][그리고2]< A[x1][그리고1]
제약:
- 1? 에이ij? 109
- 1? N ? 103
예:
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 이 문제를 해결하려면 다음 사항을 알아야 합니다.
- BIT(Binary Indexed Tree)를 사용하여 1D 배열에서 반전 쌍 수 찾기 https://www.geeksforgeeks.org/dsa/inversion-count-in-array-using-bit/
- 2D 비트 https://www.geeksforgeeks.org/dsa/two-Dimensional-binary-indexed-tree-or-fenwick-tree/
행렬에서 반전 쌍의 수를 찾아야 하기 때문에 가장 먼저 해야 할 일은 행렬의 요소를 다른 배열 v에 저장하고 배열 v를 정렬하여 정렬되지 않은 행렬의 요소를 v와 비교하고 BIT를 사용하여 반전 쌍의 수를 찾는 것입니다. 그러나 요소의 값은 매우 크다고 가정합니다(109) 따라서 행렬의 요소 값을 BIT의 인덱스로 사용할 수 없습니다. 따라서 우리는 2D BIT에서 요소의 위치를 인덱스로 사용해야 합니다.
우리는 행렬의 각 요소에 대해 튜플(-A[i][j] i j)을 사용하고 이를 'v'라는 배열에 저장할 것입니다. 그런 다음 행렬의 가장 큰 요소가 인덱스 0에 저장되고 가장 작은 요소가 v의 마지막 인덱스에 저장되도록 -A[i][j] 값에 따라 v를 오름차순으로 정렬해야 합니다. 이제 문제는 1D 배열에서 반전 쌍을 찾는 것으로 축소됩니다. 유일한 예외는 2D BIT를 사용한다는 것입니다.
여기서 우리는 v를 왼쪽에서 오른쪽으로, 즉 행렬의 가장 큰 숫자에서 가장 작은 숫자로 순회할 것이기 때문에 A[i][j]의 음수 값을 사용하고 있습니다(BIT를 사용하여 1D 배열에서 반전 쌍을 찾을 때 수행하는 작업이기 때문입니다). 양수 값을 사용하고 v를 오른쪽에서 왼쪽으로 탐색할 수도 있으며 최종 결과는 동일하게 유지됩니다.
알고리즘 :
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.
구현:
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
산출
The number of inversion pairs are : 43
시간 복잡도 : O(로그(NxN)) 여기서 N은 행렬의 크기입니다.
공간 복잡도 : 오(NxN)
퀴즈 만들기