当前位置: 面试刷题>> 数组中两个数字的最大异或 (经典算法题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 示例代码

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

码小课网站中有更多相关内容分享给大家学习,包括算法基础、数据结构、面试技巧等,欢迎访问学习。

推荐面试题