LeetCode题练习与总结：数组中两个数的最大异或值--421

一、题目描述

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

提示：

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1

二、解题思路

这个问题可以通过字典树（Trie）来解决。字典树是一种树形结构，用于高效地存储和检索字符串数据集中的键。在这个问题中，我们可以将每个整数的二进制表示视为字符串，然后构建一个字典树来存储这些二进制字符串。

步骤如下：

将所有数字转换为二进制字符串，并从最高位开始构建字典树。
对于每个数字，尝试找到字典树中与之异或结果最大的数字。具体来说，就是从最高位开始，尽可能选择与当前位相反的路径（如果存在的话）。
记录过程中遇到的最大异或结果。

三、具体代码

class Solution {class TrieNode {TrieNode[] children = new TrieNode[2];}public int findMaximumXOR(int[] nums) {// 初始化字典树的根节点TrieNode root = new TrieNode();// 将所有数字插入字典树for (int num : nums) {TrieNode cur = root;for (int i = 31; i >= 0; i--) {int bit = (num >> i) & 1;if (cur.children[bit] == null) {cur.children[bit] = new TrieNode();}cur = cur.children[bit];}}int max_xor = 0;// 对于每个数字，尝试找到与之异或结果最大的数字for (int num : nums) {TrieNode cur = root;int xor = 0;for (int i = 31; i >= 0; i--) {int bit = (num >> i) & 1;// 尝试选择与当前位相反的路径if (cur.children[1 - bit] != null) {xor = (xor << 1) | 1;cur = cur.children[1 - bit];} else {xor = xor << 1;cur = cur.children[bit];}}max_xor = Math.max(max_xor, xor);}return max_xor;}
}

这段代码首先构建了一个字典树，然后对于每个数字，通过字典树找到了与之异或结果最大的数字，并记录下最大异或结果。最终返回这个最大异或结果。

四、时间复杂度和空间复杂度

1. 时间复杂度

构建字典树：对于数组中的每个数字，我们需要遍历它的32位（假设整数为32位），并将每一位插入到字典树中。如果数组长度为n，那么构建字典树的时间复杂度为O(n * 32)。
查找最大异或值：同样地，对于数组中的每个数字，我们需要遍历它的32位，并在字典树中查找与之异或结果最大的数字。这个过程的时间复杂度也是O(n * 32)。

将这两个步骤合并，总的时间复杂度为O(n * 32)，可以简化为O(n)。

2. 空间复杂度

字典树节点：在最坏的情况下，如果所有数字的二进制表示都不同，字典树中的节点数将达到最大。每个数字有32位，每一位有两种可能（0或1），所以字典树中的节点数最多为2^32，这是一个常数，与输入数组的大小无关。
字典树结构：字典树的结构本身不依赖于输入数组的大小，它只依赖于数字的位数，这里为32位。

因此，空间复杂度为O(1)，即常数空间复杂度，因为字典树的大小不会随着输入数组的大小而变化。

五、总结知识点

字典树（Trie）：
- 字典树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。
- 在这个问题中，字典树用于存储数字的二进制表示。
位操作：
- 使用位操作来获取数字的每一位，例如 (num >> i) & 1 用于获取数字 num 的第 i 位。
- 使用位移操作 << 和按位或操作 | 来构建异或结果。
递归与迭代：
- 代码中使用了迭代而非递归来遍历字典树。
贪心算法：
- 在寻找最大异或值时，代码采用了贪心策略，即每次都试图选择与当前位相反的路径，以获得更大的异或值。
树的遍历：
- 通过遍历字典树来查找与给定数字异或结果最大的数字。
数组的使用：
- TrieNode 类中的 children 数组用于存储子节点，每个节点有两个子节点，分别对应二进制位 0 和 1。
类的定义与实例化：
- TrieNode 类的定义和实例化，以及它在 Solution 类中的使用。
循环与条件判断：
- 使用 for 循环来遍历数组中的每个数字，以及遍历数字的每一位。
- 使用 if-else 语句来决定在字典树中走哪条路径。
最大值的查找：
- 使用 Math.max 函数来更新最大异或值。