• ㊗️
• 大家
• offer
• 多多！

## Problem

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Follow up: Could you do this in O(n) runtime?

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.


Example 2:

Input: nums = [0]
Output: 0


Example 3:

Input: nums = [2,4]
Output: 6


Example 4:

Input: nums = [8,10,2]
Output: 10


Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127


## Code

class Solution {
class Node{
Node[] children;

public Node(){
children = new Node[2];
}
}

private Node root;
private int res;
public int findMaximumXOR(int[] nums) {
root = new Node();
res = Integer.MIN_VALUE;

for(int num : nums){
build(num);
}

for(int num : nums){
search(num);
}

return res;
}

private void search(int num){
Node node = root;
int sum = 0;
for(int i = 31; i >= 0; i--){
int curr = (num >> i) & 1;
if(curr == 0) {
if (node.children[1] != null) {
sum += 1 << i;
node = node.children[1];
} else {
node = node.children[0];
}
} else {
if(node.children[0] != null) {
sum += 1 << i;
node = node.children[0];
} else {
node = node.children[1];
}
}
}

res = Math.max(res, sum);
}

private void build(int num){
Node node = root;

for(int i = 31; i >= 0; i--){
// 从高位向地位建树
int curr = (num >> i) & 1;
if(node.children[curr] == null){
node.children[curr] = new Node();
}

node = node.children[curr];
}
}
}