数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中数组元素与另一个数组元素进行异或运算的最大值
在这个问题中，我们给定两个分别包含 n 个元素的数组 A 和 B。我们的任务是创建一个程序来查找每个数组元素与另一个数组元素进行异或运算可能获得的最大值。
我们必须计算数组 A 中每个元素与数组 B 中元素进行异或运算的最大值，即对于数组 A 中的每个元素，我们将在数组 B 中选择一个与之进行异或运算后得到最大值的元素。
让我们举个例子来理解这个问题 -
输入 -
array A = {3, 6 ,11, 9}
array B = {8, 2, 4, 1}输出 -
11 14 15 13
解释 -
让我们看看数组 A 中每个元素与数组 B 中所有元素进行异或运算的组合，然后为每个元素选择最大值。
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.
为了解决这个问题，一个简单且朴素的方法是计算所有可能的组合，并打印出如上例所示的最大异或值。
但这效率不高，因为代码依赖于两个循环，这使得其复杂度为 O(n^2)。
因此，我们将看到一个更好的解决方案。
它使用 Trie 数据结构，该结构将存储数组 B 中所有元素的二进制表示，以便与数组 A 中的元素进行匹配，从而找到最大异或值。
因此，对于数组 A 中的一个元素，我们将检查其最高有效位并尝试将其设为 1。然后转到下一个最高有效位。遵循此操作，我们将获得数组 B 中与 A 中某个元素进行异或运算后的最大异或元素。
示例
查找数组元素与另一个数组元素进行异或运算可能获得的最大值的程序
#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
更新于: 2020年6月3日
358 次浏览
广告