当前位置： 面试刷题>> 数组中两个数字的最大异或 (经典算法题500道)
### 完整题目描述
给定一个非空整数数组 `nums`，数组中的元素都在 `[0, 2^31 - 1]` 的范围内。请找到数组中任意两个数字的最大异或值（XOR）。
**注意**：
- 数组中的元素可以重复使用。
- 你需要返回的是两个数字的最大异或值，而不是它们的索引。
### 示例
**输入**：`nums = [3, 10, 5, 25, 2, 8]`
**输出**：`28`
**解释**：
- `3 ^ 10 = 13`
- `3 ^ 5 = 6`
- `3 ^ 25 = 26`
- `3 ^ 2 = 1`
- `3 ^ 8 = 11`
- `10 ^ 5 = 15`
- `10 ^ 25 = 27`
- `10 ^ 2 = 8`
- `10 ^ 8 = 2`
- `5 ^ 25 = 20`
- `5 ^ 2 = 7`
- `5 ^ 8 = 13`
- `25 ^ 2 = 23`
- `25 ^ 8 = 17`
- `2 ^ 8 = 10`
最大的异或值是 `27 ^ 8 = 28`（注意这不是唯一的组合）。
### 解题思路
这个问题可以通过位运算和前缀树（Trie树）来解决。基本思路是遍历数组中的每个数字，对于每个数字，我们尝试将其与数组中的其他数字进行异或运算，以找到最大的异或值。由于直接比较的时间复杂度较高，我们可以利用前缀树来优化查找过程。
### PHP 示例代码
```php
class TrieNode {
public $children = [];
public function __construct() {
$this->children = array_fill(0, 32, null);
}
}
function findMaximumXOR($nums) {
$root = new TrieNode();
$maxXOR = 0;
// 构建前缀树
foreach ($nums as $num) {
$node = $root;
for ($i = 31; $i >= 0; $i--) {
$bit = ($num >> $i) & 1;
if (!$node->children[$bit]) {
$node->children[$bit] = new TrieNode();
}
$node = $node->children[$bit];
}
}
// 查找最大异或值
foreach ($nums as $num) {
$node = $root;
$xor = 0;
for ($i = 31; $i >= 0; $i--) {
$bit = ($num >> $i) & 1;
$oppositeBit = 1 - $bit;
if ($node->children[$oppositeBit]) {
$xor |= (1 << $i);
$node = $node->children[$oppositeBit];
} else {
$node = $node->children[$bit];
}
}
$maxXOR = max($maxXOR, $xor);
}
return $maxXOR;
}
// 示例用法
$nums = [3, 10, 5, 25, 2, 8];
echo findMaximumXOR($nums); // 输出 28
```
### Python 示例代码
```python
class TrieNode:
def __init__(self):
self.children = [None] * 2
def findMaximumXOR(nums):
root = TrieNode()
max_xor = 0
# 构建前缀树
for num in nums:
node = root
for i in range(31, -1, -1):
bit = (num >> i) & 1
if not node.children[bit]:
node.children[bit] = TrieNode()
node = node.children[bit]
# 查找最大异或值
for num in nums:
node = root
xor = 0
for i in range(31, -1, -1):
bit = (num >> i) & 1
opposite_bit = 1 - bit
if node.children[opposite_bit]:
xor |= (1 << i)
node = node.children[opposite_bit]
else:
node = node.children[bit]
max_xor = max(max_xor, xor)
return max_xor
# 示例用法
nums = [3, 10, 5, 25, 2, 8]
print(findMaximumXOR(nums)) # 输出 28
```
### JavaScript 示例代码
```javascript
class TrieNode {
constructor() {
this.children = new Array(2).fill(null);
}
}
function findMaximumXOR(nums) {
const root = new TrieNode();
let maxXOR = 0;
// 构建前缀树
for (const num of nums) {
let node = root;
for (let i = 31; i >= 0; i--) {
const bit = (num >> i) & 1;
if (!node.children[bit]) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
}
}
// 查找最大异或值
for (const num of nums) {
let node = root;
let xor = 0;
for (let i = 31; i >= 0; i--) {
const bit = (num >> i) & 1;
const oppositeBit = 1 - bit;
if (node.children[oppositeBit]) {
xor |= (1 << i);
node = node.children[oppositeBit];
} else {
node = node.children[bit];
}
}
maxXOR = Math.max(maxXOR, xor);
}
return maxXOR;
}
// 示例用法
const nums = [3, 10, 5, 25, 2, 8];
console.log(findMaximumXOR(nums)); // 输出 28
```
码小课网站中有更多相关内容分享给大家学习，包括算法基础、数据结构、面试技巧等，欢迎访问学习。