資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告