数组中每个元素与C ++中另一个数组的最大可能XOR
在这个问题中，我们给了两个数组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;
}输出结果
The maximum possible XOR of every possible element in array A with Array B is 11 15 14 13