2021-05-14：给定一个数组arr，想知道arr中哪两个数的异或结果最大。返回最大的异或结果。

2021-05-14：给定一个数组arr，想知道arr中哪两个数的异或结果最大。返回最大的异或结果。

福大大 答案2021-05-14：

前缀树。一个数，用二进制表示，0走左边分支，1走右边分支。准备一个max变量，遍历的时候，遇到比max还要大的，max更新。最后返回max。
时间复杂度：O(N)。

代码用golang编写。代码如下：

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
    }
}

执行结果如下：

左神java代码