在C ++中找到具有最大位差的二进制矩阵中的行对

假设我们有一个二进制矩阵；我们必须找到给定矩阵中具有最大位差的一对行。

因此，如果输入像矩阵，则输出为[2,3]，因为第2行和第3行之间的位差为4，这是最大值。

• 为了解决这个问题，我们将遵循以下步骤-

• 定义Trie结构，包含值和两个子代。

• 定义一个函数get_max_bit_diff()，它将取特里，矩阵，n，row_index的根，

• temp：= root，count：= 0

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• temp：= temp的child [1- matrix [row_index，i]]

• （增加1）

• temp：= temp的child [matrix [row_index，i]]

• 如果temp的child [matrix [row_index，i]]不为NULL，则-

• 否则，当temp的child [1-matrix [row_index，i]]不为NULL时，则-

• leaf_index：=临时叶

• temp_count：= 0，temp：=根

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• temp：= temp的child [matrix [row_index，i]]

• temp：= temp的child [1- matrix [row_index，i]]

• （将temp_count增加1）

• 如果temp的child [1-matrix [row_index，i]]不为NULL，则-

• 否则，当temp的child [matrix [row_index，i]]不为NULL时，则-

• P =如果temp_count> count，则使用（temp_count，temp的叶子）配对，否则使用(count,leaf_index)进行配对

• 返回P

• 从主要方法中，执行以下操作-

• 根=一个新的TrieNode

• 在根目录中插入第0行

• max_bit_diff：= -inf

• 定义一对pr和另一对temp

• 对于初始化i：= 1，当i <n时，更新（将i增加1），-

• max_bit_diff：=温度优先

• pr：=使用（temp.second，i + 1）配对

• 温度：= get_max_bit_diff(root,mat,m,i)

• 如果max_bit_diff <temp的第一个，则-

• 将第i行插入根目录

• 显示对

范例（C ++）

让我们看下面的实现以更好地理解-

#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
class TrieNode {
   public:
   int leaf;
   TrieNode *child[2];
   TrieNode(){
      leaf = 0;
      child[0] = child[1] = NULL;
   }
};
void insert(TrieNode *root, int matrix[][MAX], int n, int row_index){
   TrieNode * temp = root;
   for (int i=0; i<n; i++) {
      if(temp->child[ matrix[row_index][i] ] == NULL)
         temp->child[ matrix[row_index][i] ] = new TrieNode();
         temp = temp->child[ matrix[row_index][i] ];
      }
      temp->leaf = row_index +1 ;
   }
   pair<int, int>get_max_bit_diff(TrieNode * root, int matrix[][MAX], int n, int row_index) {
      TrieNode * temp = root;
      int count = 0;
      for (int i= 0 ; i < n ; i++) {
         if (temp->child[ matrix[row_index][i] ] != NULL)
            temp = temp->child[ matrix[row_index][i] ];
         else if (temp->child[1 - matrix[row_index][i]] != NULL) {
            temp = temp->child[1- matrix[row_index][i]];
            count++;
         }
      }
      int leaf_index = temp->leaf;
      int temp_count = 0 ;
      temp = root;
      for (int i= 0 ; i < n ; i++) {
         if (temp->child[ 1 - matrix[row_index][i] ] !=NULL) {
            temp = temp->child[ 1- matrix[row_index][i] ];
            temp_count++;
         }
         else if (temp->child[ matrix[row_index][i] ] != NULL)
            temp = temp->child[ matrix[row_index][i] ];
      }
      pair <int ,int> P = temp_count > count ? make_pair(temp_count, temp->leaf): make_pair(count, leaf_index);
      return P;
}
void get_max_diff( int mat[][MAX], int n, int m) {
   TrieNode * root = new TrieNode();
   insert(root, mat, m, 0);
   int max_bit_diff = INT_MIN;
   pair<int ,int> pr, temp ;
   for (int i = 1 ; i < n; i++) {
      temp = get_max_bit_diff(root, mat, m ,i);
      if (max_bit_diff < temp.first ) {
         max_bit_diff = temp.first;
         pr = make_pair( temp.second, i+1);
      }
      insert(root, mat, m, i );
   }
   cout << "(" << pr.first <<", "<< pr.second << ")";
}
int main() {
   int mat[][MAX] = {
      {1 ,1 ,1 ,1 },
      {1, 0, 1 ,1},
      {0 ,1 ,0 ,0},
      {1 ,0 ,0 ,0}
   };
   get_max_diff(mat, 4, 4) ;
}

输入值

{{1 ,1 ,1 ,1 },
{1, 0, 1 ,1},
{0 ,1 ,0 ,0},
{1 ,0 ,0 ,0}}, 4,4

输出结果

(2,3)