数组中每个元素与C ++中另一个数组的最大可能XOR

Z时代
2024-01-10
分类：综合

在这个问题中，我们给了两个数组A和B，每个数组由n个元素组成。我们的任务是创建一个程序，以查找数组中每个元素与另一个数组的最大可能XOR。

我们必须计算数组A与数组B的每个元素的最大XOR，即对于数组A的每个元素，我们将选择数组B中具有最大XOR值的元素。

让我们以一个例子来了解问题-

输入-

array A = {3, 6 ,11, 9}
array B = {8, 2, 4, 1}

输出-

11 14 15 13

说明-

让我们看一下数组A的每个元素与数组B的所有元素的XOR组合，然后为每个元素选择最大值。

3 XOR 8 = 11 3 XOR 2 = 1 3 XOR 4 = 7 3 XOR 1 = 2
Maximum = 11.
6 XOR 8 = 14 6 XOR 2 = 4 6 XOR 4 = 2 6 XOR 1 = 1
Maximum = 14.
11 XOR 8 = 3 11 XOR 2 = 9 11 XOR 4 = 15 11 XOR 1 = 10
Maximum = 15.
9 XOR 8 = 1 9 XOR 2 = 11 9 XOR 4 = 13 9 XOR 1 = 8
Maximum = 13.

为了解决这个问题，一种简单而幼稚的方法是计算所有组合并打印出最大的XOR，如上面的示例所示。

但这将无效，因为代码依赖于两个循环，这使得其复杂度为O（n ^ 2）。

因此，我们将看到一个更好的解决方案。

它使用trie数据结构，该结构将存储数组B的所有元素的二进制数以与数组A进行匹配，以找到最大XOR。

因此，对于数组A的元素，我们将检查其最高有效位并尝试使其变为1。然后转到下一个MSB。接下来，我们将获得数组B中A元素的最大XOR元素。

示例

程序查找数组中每个元素与另一个数组的最大可能XOR

#include<iostream>
using namespace std;
struct trie{
   int value;
   trie *child[2];
};
trie * get(){
   trie * root = new trie;
   root -> value = 0;
   root -> child[0] = NULL;
   root -> child[1] = NULL;
   return root;
}
void insert(trie * root, int key){
   trie * temp = root;
   for (int i = 31; i >= 0; i--){
      bool current_bit = key & (1 << i);
      if (temp -> child[current_bit] == NULL)
         temp -> child[current_bit] = get();
      temp = temp -> child[current_bit];
   }
   temp -> value = key;
}
int findMaxXor(trie * root, int element){
   trie * temp = root;
   for (int i = 31; i >= 0; i--){
      bool bits = ( element & ( 1 << i) );
      if (temp -> child[1 - bits] != NULL)
         temp = temp -> child[1 - bits];
      else
         temp = temp -> child[bits];
   }
   return (element ^ temp -> value);
}
int main(){
   int A[] = {3, 11, 6, 9};
   int B[] = {8, 2, 4, 1};
   int N = sizeof(A)/sizeof(A[0]);
   trie * root = get();
   for (int i = 0; i < N; i++)
   insert(root, B[i]);
   cout<<"The maximum possible XOR of every possible element in array A with Array B is\n";
   for (int i = 0; i < N; i++)
   cout <<findMaxXor(root, A[i])<<"\t";
   return 0;
}