0421. Maximum XOR of Two Numbers in an Array ============================================= 题目信息 -------- :题号: 0421 :难度: Medium :主题: 非负整数、按位异或、二元选择、最大结果 :原题: `LeetCode 0421 `_ :重点: 从数组中选择两个下标 ``i <= j``、计算完整整数的按位异或、只返回最大异或值 题目重述 -------- 给定非负整数数组 ``nums``,在所有满足 ``0 <= i <= j < nums.length`` 的下标对中,计算 ``nums[i] XOR nums[j]``,返回能够得到的最大值。 ``nums.length`` 位于 ``[1, 2 * 10^5]``,每个元素位于 ``[0, 2^31-1]``。允许 ``i == j``,此时异或结果为 0;当数组中有多个下标对取得同一最大值时,仍只返回该最大整数,不需要返回下标或元素。 自建示例 -------- 最大值来自不同大小的两个数: .. code-block:: text 输入:nums = [2, 7, 10] 输出:13 解释:7 XOR 10 = 13,大于 2 XOR 7 = 5 和 2 XOR 10 = 8,因此最大异或值为 13。 只有一个元素: .. code-block:: text 输入:nums = [19] 输出:0 解释:唯一允许的下标对是 i = j = 0,任何整数与自身异或都等于 0。 按最高位贪心保留可行前缀 -------------------------- 异或结果的高位比低位重要。将所有数插入二进制 trie 后,查询一个数时从最高位到最低位尽量选择与当前位相反的分支:若该分支存在,就能让这一位为 1;否则只能走相同位。因为高位决策优先级更高,这样得到与该数配对的最大异或值。 数组值不超过 ``2^31-1``,从第 30 位向下检查即可;允许同一个下标配对不会影响结果,至少一个数时最大值也会由查询得到。 C++ 实现 -------- .. code-block:: cpp class Solution { struct Node { int child[2] = {-1, -1}; }; std::vector trie; void insert(int value) { int node = 0; for (int bit = 30; bit >= 0; --bit) { int current = (value >> bit) & 1; if (trie[node].child[current] == -1) { trie[node].child[current] = static_cast(trie.size()); trie.push_back(Node()); } node = trie[node].child[current]; } } int bestWith(int value) const { int node = 0; int result = 0; for (int bit = 30; bit >= 0; --bit) { int current = (value >> bit) & 1; int wanted = current ^ 1; if (trie[node].child[wanted] != -1) { result |= 1 << bit; node = trie[node].child[wanted]; } else { node = trie[node].child[current]; } } return result; } public: int findMaximumXOR(std::vector& nums) { trie.clear(); trie.push_back(Node()); for (int value : nums) insert(value); int answer = 0; for (int value : nums) { answer = std::max(answer, bestWith(value)); } return answer; } }; 代码分析 -------- Trie 中的每条路径代表一个完整数的位前缀;查询优先尝试相反位,若存在就不会牺牲已确定的高位最优性。插入和查询各检查 31 位,时间复杂度为 ``O(31n)``,额外空间为 ``O(31n)``。