LeetCode 421. 数组中两个数的最大异或值

Categories:

题目描述
思路分析
1. 解法一：二进制字典树（推荐）
相似题目

题目描述

✅ 421. 数组中两个数的最大异或值

思路分析

解法一：二进制字典树（推荐）

核心思路：

构建 0/1 字典树，按位插入所有数字。

对每个数从高位到低位贪心选择相反位以最大化异或。

取最大结果即为答案。

复杂度分析：

时间复杂度：O(n * B)，其中 n 表示数组长度，B 为位数（31）。

空间复杂度：O(n * B)，字典树存储所有位。

class Solution {
    private static class Node {
        Node[] next = new Node[2];
    }

    public int findMaximumXOR(int[] nums) {
        Node root = new Node();

        // 插入所有数字
        for (int num : nums) {
            Node cur = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (cur.next[bit] == null) {
                    cur.next[bit] = new Node();
                }
                cur = cur.next[bit];
            }
        }

        int ans = 0;

        // 查询最大异或
        for (int num : nums) {
            Node cur = root;
            int val = 0;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                int want = bit ^ 1;

                if (cur.next[want] != null) {
                    val |= (1 << i);
                    cur = cur.next[want];
                } else {
                    cur = cur.next[bit];
                }
            }
            ans = Math.max(ans, val);
        }

        return ans;
    }
}

type TrieNode struct {
	next [2]*TrieNode
}

func findMaximumXOR(nums []int) int {
	root := &TrieNode{}

	// 插入所有数字
	for _, num := range nums {
		cur := root
		for i := 31; i >= 0; i-- {
			bit := (num >> i) & 1
			if cur.next[bit] == nil {
				cur.next[bit] = &TrieNode{}
			}
			cur = cur.next[bit]
		}
	}

	ans := 0

	// 查询最大异或
	for _, num := range nums {
		cur := root
		val := 0
		for i := 31; i >= 0; i-- {
			bit := (num >> i) & 1
			want := bit ^ 1
			if cur.next[want] != nil {
				val |= 1 << i
				cur = cur.next[want]
			} else {
				cur = cur.next[bit]
			}
		}
		if val > ans {
			ans = val
		}
	}

	return ans
}

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	Trie
1707. 与数组中元素的最大异或值	困难	Trie
421. 数组中两个数的最大异或值	中等	Trie
1310. 子数组异或查询	中等	前缀异或
2680. 最大或值	中等	位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/82578647