What is the optimal approach to solving the Maximum XOR of Two Numbers in an Array problem?

The optimal approach combines bit manipulation with a trie data structure or a hash set to efficiently compute the maximum XOR value in O(n * L) time.

How do I reduce the time complexity for Maximum XOR of Two Numbers in an Array?

To reduce time complexity, use a trie or hash set for faster lookups, avoiding the need to check every pair of numbers.

What is the trade-off between using a hash table versus a trie for this problem?

Using a hash table may offer a simpler solution but can be less efficient in terms of space, while a trie can provide a more structured and efficient space-time trade-off.

How does bitwise XOR work in this problem?

XOR compares the binary representation of two numbers and returns a result where each bit is 1 if the bits of the two numbers differ, and 0 if they are the same.

What are some edge cases I should consider when solving this problem?

Edge cases include arrays with only one element, arrays with identical elements, and ensuring the algorithm handles large arrays efficiently.

#421

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

数组中两个数的最大异或值

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j 。示例 1：输入： nums = [3,10,5,25,2,8] 输出： 28 解释：最大运算结果是 5 XOR 25 = 28. 示例 2：输入： nums = [14,7…

数组哈希表位运算字典树

题目描述

给你一个整数数组 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⁵
0 <= nums[i] <= 2³¹ - 1

lightbulb

解题思路

方法一：前缀树

题目是求两个元素的异或最大值，可以从最高位开始考虑。

我们把数组中的每个元素 $x$ 看作一个 $32$ 位的 $01$ 串，按二进制从高位到低位的顺序，插入前缀树（最低位为叶子节点）。

搜索 $x$ 时，尽量走相反的 $01$ 字符指针的策略，因为异或运算的法则是相同得 $0$ ，不同得 $1$ ，所以我们尽可能往与 $x$ 当前位相反的字符方向走，才能得到能和 $x$ 产生最大异或值的结果。

时间复杂度 $O(n \times \log M)$ ，空间复杂度 $O(n \times \log M)$ ，其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组中元素的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

class Trie:
    __slots__ = ("children",)

    def __init__(self):
        self.children: List[Trie | None] = [None, None]

    def insert(self, x: int):
        node = self
        for i in range(30, -1, -1):
            v = x >> i & 1
            if node.children[v] is None:
                node.children[v] = Trie()
            node = node.children[v]

    def search(self, x: int) -> int:
        node = self
        ans = 0
        for i in range(30, -1, -1):
            v = x >> i & 1
            if node.children[v ^ 1]:
                ans |= 1 << i
                node = node.children[v ^ 1]
            else:
                node = node.children[v]
        return ans


class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        trie = Trie()
        for x in nums:
            trie.insert(x)
        return max(trie.search(x) for x in nums)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate can demonstrate knowledge of bitwise operations and their applications in optimization problems.
question_mark
Candidate shows ability to use a trie structure for efficient lookups and optimizations.
question_mark
Candidate understands the trade-offs between different approaches in terms of time and space complexity.

warning

常见陷阱

外企场景

error
Not considering the importance of bit-level operations, which can lead to inefficient brute force solutions.
error
Failing to optimize the space complexity when using a hash set or trie to store intermediate results.
error
Overlooking edge cases, such as arrays with only one element or arrays containing only the same number.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Solving the problem without using a trie, relying solely on hash-based solutions.
arrow_right_alt
Modifying the problem to consider an array of very large numbers, affecting time complexity.
arrow_right_alt
Finding the maximum XOR value for subarrays instead of the entire array.

help

常见问题

外企场景

继续练习

#1178 猜字谜 #491 非递减子序列 #336 回文对