ZÄHLEN SIE INVERSIONSPAARE IN EINER MATRIX

Gegeben sei eine Matrix A der Größe NxN Wir müssen die Anzahl der darin enthaltenen Inversionspaare ermitteln. Die Inversionsanzahl in einer Matrix ist definiert als die Anzahl der Paare, die die folgenden Bedingungen erfüllen:

X₁? X₂
Und₁? Und₂
Axt₂][Und₂]< A[x₁][Und₁]

Einschränkungen:

1 ? A_ij? 10⁹
1 ? N ? 10³

Beispiele:

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

Um dieses Problem zu lösen, müssen wir Folgendes wissen:

Ermitteln der Anzahl von Inversionspaaren in einem 1D-Array mithilfe des 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 wir die Anzahl der Inversionspaare in einer Matrix ermitteln müssen, müssen wir zunächst die Elemente der Matrix in einem anderen Array, beispielsweise v, speichern und das Array v sortieren, damit wir die Elemente der unsortierten Matrix mit v vergleichen und die Anzahl der Inversionspaare mithilfe von BIT ermitteln können. Es wird jedoch vorausgesetzt, dass die Werte der Elemente sehr groß sind (10⁹), sodass wir die Werte der Elemente in der Matrix nicht als Indizes im BIT verwenden können. Daher müssen wir die Position der Elemente als Indizes im 2D-BIT verwenden.

Wir werden das Tupel (-A[i][j] i j) für jedes Element der Matrix verwenden und es in einem Array speichern, sagen wir „v“. Dann müssen wir v nach dem Wert von -A[i][j] in aufsteigender Reihenfolge sortieren, sodass das größte Element der Matrix am Index 0 und das kleinste am letzten Index von v gespeichert wird. Jetzt reduziert sich das Problem darauf, Inversionspaare in einem 1D-Array zu finden. Die einzige Ausnahme besteht darin, dass wir ein 2D-BIT verwenden werden.

Beachten Sie, dass wir hier negative Werte von A[i][j] verwenden, einfach weil wir v von links nach rechts durchlaufen, d. h. von der größten Zahl in der Matrix zur kleinsten (weil wir das tun, wenn wir Inversionspaare in einem 1D-Array mit BIT finden). Man kann auch positive Werte verwenden und v von rechts nach links durchlaufen, sodass das Endergebnis gleich bleibt.

Algorithmus:

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.

Durchführung:

C++

// C++ program to count the number of inversion // pairs in a 2D matrix #include    using namespace std; // for simplicity we are taking N as 4 #define N 4 void update(int l int r int val int bit[][N + 1]) {  for (int i = l; i <= N; i += i & -i)  for (int j = r; j <= N; j += j & -j)  bit[i][j] += val; } // function to find cumulative sum upto // index (l r) in the 2D BIT long long query(int l int r int bit[][N + 1]) {  long 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; } // function to count and return the number // of inversion pairs in the matrix long long countInversionPairs(int mat[][N]) {  // the 2D bit array and initialize it with 0.  int bit[N+1][N+1] = {0};  // v will store the tuple (-mat[i][j] i j)  vector<pair<int pair<int int> > > v;  // store the tuples in the vector v  for (int i = 0; i < N; ++i)  for (int j = 0; j < N; ++j)  v.push_back(make_pair(-mat[i][j]  make_pair(i+1 j+1)));  sort(v.begin() v.end());  // inv_pair_cnt will store the number of  // inversion pairs  long long inv_pair_cnt = 0;  // traverse all the tuples of vector v  int i = 0;  while (i < v.size())  {  int curr = i;  vector<pair<int int> > pairs;  while (curr < v.size() &&  (v[curr].first == v[i].first))  {  // push the position of the current element in 'pairs'  pairs.push_back(make_pair(v[curr].second.first  v[curr].second.second));  inv_pair_cnt += query(v[curr].second.first  v[curr].second.second bit);  curr++;  }  vector<pair<int int> >::iterator it;  // traverse the 'pairs' vector  for (it = pairs.begin(); it != pairs.end(); ++it)  {  int x = it->first;  int y = it->second;  // update the position (x y) by 1  update(x y 1 bit);  }  i = curr;  }  return inv_pair_cnt; } // Driver program int main() {  int mat[N][N] = { { 4 7 2 9 }  { 6 4 1 7 }  { 5 3 8 1 }  { 3 2 5 6 } };  long long inv_pair_cnt = countInversionPairs(mat);  cout << 'The number of inversion pairs are : '  << inv_pair_cnt << endl;  return 0; }

Python3

# 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

// 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

Java

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

Ausgabe

The number of inversion pairs are : 43

Zeitkomplexität : O(log(NxN)) wobei N die Größe der Matrix ist
Weltraumkomplexität : O(NxN)

Quiz erstellen

TechCodeview

Zählen Sie Inversionspaare in einer Matrix