2021-05-14：给定一个数组arr，想知道arr中哪两个数的异或结果最大。返回最大的异或结果。
福大大 答案2021-05-14：
前缀树。一个数，用二进制表示，0走左边分支，1走右边分支。准备一个max变量，遍历的时候，遇到比max还要大的，max更新。最后返回max。
时间复杂度：O(N)。
代码用golang编写。代码如下：
代码语言：txt复制package main
import (
"fmt"
"math"
)
func main() {
arr := []int{3, 10, 5, 25, 2, 8}
ret := findMaximumXOR(arr)
fmt.Println(ret)
}
func findMaximumXOR(arr []int) int {
if len(arr) < 2 {
return 0
}
max := math.MinInt64
numTrie := NewNumTrie()
numTrie.add(arr[0])
for i := 1; i < len(arr); i {
max = getMax(max, numTrie.maxXor(arr[i]))
numTrie.add(arr[i])
}
return max
}
type Node struct {
nexts []*Node
}
func NewNode() *Node {
ret := &Node{}
ret.nexts = make([]*Node, 2)
return ret
}
// 基于本题，定制前缀树的实现
type NumTrie struct {
// 头节点
head *Node
}
func NewNumTrie() *NumTrie {
ret := &NumTrie{}
ret.head = NewNode()
return ret
}
func (this *NumTrie) add(newNum int) {
cur := this.head
for move := 63; move >= 0; move-- {
path := (newNum >> move) & 1
if cur.nexts[path] == nil {
cur.nexts[path] = NewNode()
}
cur = cur.nexts[path]
}
}
// 该结构之前收集了一票数字，并且建好了前缀树
// num和 谁 ^ 最大的结果（把结果返回）
func (this *NumTrie) maxXor(num int) int {
cur := this.head
ans := 0
for move := 63; move >= 0; move-- {
// 取出num中第move位的状态，path只有两种值0就1，整数
path := (num >> move) & 1
// 期待遇到的东西
best := twoSelectOne(move == 63, path, path^1)
// 实际遇到的东西
best = twoSelectOne(cur.nexts[best] != nil, best, best^1)
// (path ^ best) 当前位位异或完的结果
ans |= (path ^ best) << move
cur = cur.nexts[best]
}
return ans
}
func twoSelectOne(condition bool, a int, b int) int {
if condition {
return a
} else {
return b
}
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
image.png左神java代码
