LeetCode-421. Maximum XOR of Two Numbers in an Array

LeetCode-421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]Output: 28Explanation: The maximum result is 5 ^ 25 = 28.

题解：

参考讨论区的前缀树做法：

建树

因为二进制元素只有0,1。考虑使用二叉树来构建前缀树。

根节点为符号位0从高位到低位依次构建左子树为1节点，又子树为0节点​​​[3,10,5,25,2,8]​​ 按照以上规则构建如下图（省略高位0）

那么这颗树包含了数组中所有的数字，从根节点到叶子节点的一条路径表示数组中的一个十进制数的二进制编码。

找最大异或值

对于​​25​​​ (​​0000 0000 0000 0000 0000 0000 0001 1001​​​) 而言，从第31-6位（都是正数，不考虑符号位），都为0,，且数组中的数字31-6位都为0，因此最大异或结果31-6位只能为0。 当前使得异或结果最大的数​​​x​​​为​​0000 0000 0000 0000 0000 0000 000? ????​​​ 当前指针​​curNode​​指向第图中根节点。 从第5位开始：​​5 1​​ ​​x​​的第5位为0，则结果最大。应选择右分支，​​curNode = curNode->right​​​​4 1​​ ​​x​​的第4位为0，则结果最大。应选择右分支，​​curNode = curNode->right​​​​3 0​​ ​​x​​的第3位为1，则结果最大。应选择左分支，​​curNode = curNode->left​​​​2 0​​ ​​x​​的第2位为1，则结果最大。应选择左分支，但树中左分支为null，只能选择右分支​​curNode = curNode->right​​ 于是​​x​​的第2位为0。​​1 1​​ ​​x​​的第1位为0，则结果最大。应选择右分支，但树中右分支为null，只能选择左分支​​curNode = curNode->left​​ 于是​​x​​的第1位为1。 找到的x为5（00101）。

go：

type Trie struct { val int left *Trie right *Trie}func buildTrie(nums []int) *Trie { n := len(nums) trie := &Trie{0, nil, nil} var t *Trie for i := 0; i < n; i++ { t = trie for j := 31; j >= 0; j-- { tmp := (1 << uint(j)); if tmp & nums[i] == 0 { if t.left == nil { t.left = &Trie{0, nil, nil} } t = t.left } else { if t.right == nil { t.right = &Trie{1, nil, nil} } t = t.right } } } return trie}func max(a, b int) int { if a > b { return a } return b}func findMaximumXOR(nums []int) int { trie := buildTrie(nums) res := 0 for i := 0; i < len(nums); i++ { cur := 0 t := trie for j := 31; j >= 0; j-- { tmp := 1 << uint(j) if t.left != nil && t.right != nil { if tmp & nums[i] == 0 { t = t.right } else if tmp & nums[i] != 0 { t = t.left } else { break } } else { if t.left != nil { t = t.left } else if t.right != nil { t = t.right } else { break } } cur += (tmp & nums[i]) ^ (t.val << uint(j)) } res = max(res, cur) } return res}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。