数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++数组中两数的最大异或值
假设我们有一个非空数字数组 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231。我们需要找到 ai XOR aj 的最大结果，其中 0 ≤ i, j < n。例如，如果输入为 [3, 10, 5, 15, 2, 8]，则输出为 28。最大结果为 5 XOR 25 = 28。
为了解决这个问题，我们将遵循以下步骤：
定义 insertNode() 函数，它将接收 val 和 head 作为参数。
curr := head
for i in range(31, -1, -1):
bit := (val >> i) & 1
if curr 的子节点[bit] 为空，则 curr 的子节点[bit] := 新节点
curr := curr 的子节点[bit]
定义 find() 方法。它将接收 val 和 head 作为输入。
curr := head, ans := 0
for i in range(31, -1, -1):
bit := (val >> i) & 1
if curr 的子节点[bit] 为空，则 ans := ans | (1 << i)
curr := curr 的子节点[bit]
return ans
在主方法中，执行以下操作：
ans := 0
n := nums 的大小
head := 新节点
for i in range(0, n): insertNode(nums[i], head)
for i in range(0, n): ans := max(ans, find(nums[i], head))
return ans
示例 (C++)
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
struct Node{
Node* child[2];
Node(){
child[1] = child[0] = NULL;
}
};
class Solution {
public:
void insertNode(int val, Node* head){
Node* curr = head;
for(int i = 31; i>= 0; i--){
int bit = (val >> i) & 1;
if(!curr->child[bit]){
curr->child[bit] = new Node();
}
curr = curr->child[bit];
}
}
int find(int val, Node* head){
Node* curr = head;
int ans = 0;
for(int i = 31; i>= 0; i--){
int bit = (val >> i) & 1;
if(curr->child[!bit]){
ans |= (1 << i);
curr = curr->child[!bit];
} else {
curr = curr->child[bit];
}
}
return ans;
}
int findMaximumXOR(vector<int>& nums) {
int ans = 0;
int n = nums.size();
Node* head = new Node();
for(int i = 0; i < n; i++){
insertNode(nums[i], head);
}
for(int i = 0; i < n; i++){
ans = max(ans, find(nums[i], head));
}
return ans;
}
};
main(){
vector<int> v = {3,10,5,25,2,8};
Solution ob;
cout << (ob.findMaximumXOR(v));
}输入
[3,10,5,25,2,8]
输出
28
更新于：2020年5月2日
162 次浏览
广告