完整题目描述
给定一个非空整数数组 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 示例代码
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 示例代码
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 示例代码
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
码小课网站中有更多相关内容分享给大家学习,包括算法基础、数据结构、面试技巧等,欢迎访问学习。