class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
}
};
剑指 Offer II 067. 最大的异或
给定一个整数数组 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 = [0] 输出：0
示例 3：
输入：nums = [2,4] 输出：6
示例 4：
输入：nums = [8,10,2] 输出：10
示例 5：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70] 输出：127
提示：
1 <= nums.length <= 2 * 1040 <= nums[i] <= 231 - 1
进阶：你可以在 O(n) 的时间解决这个问题吗？
注意：本题与主站 421 题相同： https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
原站题解
golang 解法, 执行用时: 236 ms, 内存消耗: 9.4 MB, 提交时间: 2022-11-20 17:41:04
func findMaximumXOR(nums []int) (x int) {
const highBit = 30 // 最高位的二进制位编号为 30
for k := highBit; k >= 0; k-- {
// 将所有的 pre^k(a_j) 放入哈希表中
seen := map[int]bool{}
for _, num := range nums {
// 如果只想保留从最高位开始到第 k 个二进制位为止的部分
// 只需将其右移 k 位
seen[num>>k] = true
}
// 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
// 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
xNext := x*2 + 1
found := false
// 枚举 i
for _, num := range nums {
if seen[num>>k^xNext] {
found = true
break
}
}
if found {
x = xNext
} else {
// 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
// 即为 x = x*2
x = xNext - 1
}
}
return
}
golang 解法, 执行用时: 136 ms, 内存消耗: 9.9 MB, 提交时间: 2022-11-20 17:40:41
const highBit = 30
type trie struct {
left, right *trie
}
func (t *trie) add(num int) {
cur := t
for i := highBit; i >= 0; i-- {
bit := num >> i & 1
if bit == 0 {
if cur.left == nil {
cur.left = &trie{}
}
cur = cur.left
} else {
if cur.right == nil {
cur.right = &trie{}
}
cur = cur.right
}
}
}
func (t *trie) check(num int) (x int) {
cur := t
for i := highBit; i >= 0; i-- {
bit := num >> i & 1
if bit == 0 {
// a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
if cur.right != nil {
cur = cur.right
x = x*2 + 1
} else {
cur = cur.left
x = x * 2
}
} else {
// a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
if cur.left != nil {
cur = cur.left
x = x*2 + 1
} else {
cur = cur.right
x = x * 2
}
}
}
return
}
func findMaximumXOR(nums []int) (x int) {
root := &trie{}
for i := 1; i < len(nums); i++ {
// 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
root.add(nums[i-1])
// 将 nums[i] 看作 ai，找出最大的 x 更新答案
x = max(x, root.check(nums[i]))
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
python3 解法, 执行用时: 3680 ms, 内存消耗: 68 MB, 提交时间: 2022-11-20 17:40:17
class Trie:
def __init__(self):
# 左子树指向表示 0 的子节点
self.left = None
# 右子树指向表示 1 的子节点
self.right = None
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
# 字典树的根节点
root = Trie()
# 最高位的二进制位编号为 30
HIGH_BIT = 30
def add(num: int):
cur = root
for k in range(HIGH_BIT, -1, -1):
bit = (num >> k) & 1
if bit == 0:
if not cur.left:
cur.left = Trie()
cur = cur.left
else:
if not cur.right:
cur.right = Trie()
cur = cur.right
def check(num: int) -> int:
cur = root
x = 0
for k in range(HIGH_BIT, -1, -1):
bit = (num >> k) & 1
if bit == 0:
# a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
if cur.right:
cur = cur.right
x = x * 2 + 1
else:
cur = cur.left
x = x * 2
else:
# a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
if cur.left:
cur = cur.left
x = x * 2 + 1
else:
cur = cur.right
x = x * 2
return x
n = len(nums)
x = 0
for i in range(1, n):
# 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
add(nums[i - 1])
# 将 nums[i] 看作 ai，找出最大的 x 更新答案
x = max(x, check(nums[i]))
return x
python3 解法, 执行用时: 864 ms, 内存消耗: 27.8 MB, 提交时间: 2022-11-20 17:39:59
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
# 最高位的二进制位编号为 30
HIGH_BIT = 30
x = 0
for k in range(HIGH_BIT, -1, -1):
seen = set()
# 将所有的 pre^k(a_j) 放入哈希表中
for num in nums:
# 如果只想保留从最高位开始到第 k 个二进制位为止的部分
# 只需将其右移 k 位
seen.add(num >> k)
# 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
# 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
x_next = x * 2 + 1
found = False
# 枚举 i
for num in nums:
if x_next ^ (num >> k) in seen:
found = True
break
if found:
x = x_next
else:
# 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
# 即为 x = x*2
x = x_next - 1
return x