题目
给定一个非空数组,数组中元素为 a0, a1, a2, … , an-1,其中 0 ≤ ai 最大的异或 (XOR) 运算结果,其中0 ≤ i, j < n 。
你能在O(n)的时间解决这个问题吗?...示例:
输入: [3, 10, 5, 25, 2, 8]
输出: 28
解释: 最大的结果是 5 ^ 25 = 28....Tries树
题目要求O(n)时间复杂度,两两异或O(n2)
考虑将每个数字的二进制位插入Trie树(从高位往低位插入)O(n)
再遍历每个数字bit,贪心从trie树的异或最大路径往下走,得到一个val...,取val的最大值,O(n)时间复杂度
class Node
{
public:
int val;
Node *next[2];
Node(int v = 0):val(v) {next[0] =