题目

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

进阶：你可以在 O(n) 的时间解决这个问题吗？

示例 1：输入：nums = [3,10,5,25,2,8] 输出：28

解释：最大运算结果是 5 XOR 25 = 28.

示例 2：输入：nums = [0] 输出：0

示例 3：输入：nums = [2,4] 输出：6

示例 4：输入：nums = [8,10,2] 输出：10

示例 5：输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70] 输出：127

提示：1 <= nums.length <= 2 * 104

0 <= nums[i] <= 231 - 1

解题思路分析

1、哈希+位运算；时间复杂度O(n)，空间复杂度O(n)

func findMaximumXOR(nums []int) int {
   res := 0
   target := 0
   for i := 31; i >= 0; i-- { // 枚举每一位（第i位，从右到左），判断该为能否为1
      m := make(map[int]bool)
      target = target | (1 << i) // target第i位置1
      for j := 0; j < len(nums); j++ {
         m[nums[j]&target] = true // 高位&：取前缀
      }
      temp := res | (1 << i) // 假设结果第i位为1
      // a ^ b = temp
      // temp ^ a = b
      for k := range m {
         if _, ok := m[temp^k]; ok {
            res = temp // 能取到1
            break
         }
      }
   }
   return res
}

2、trie树；时间复杂度O(n)，空间复杂度O(n)

func findMaximumXOR(nums []int) int {
   n := len(nums)
   if n <= 1 {
      return 0
   }
   res := 0
   root := Trie{
      next: make([]*Trie, 2), // 0和1
   }
   for i := 0; i < n; i++ {
      temp := &root
      for j := 31; j >= 0; j-- {
         value := (nums[i] >> j) & 1
         if temp.next[value] == nil {
            temp.next[value] = &Trie{
               next: make([]*Trie, 2),
            }
         }
         temp = temp.next[value]
      }
   }
   for i := 0; i < n; i++ {
      temp := &root
      cur := 0
      for j := 31; j >= 0; j-- {
         value := (nums[i] >> j) & 1
         if temp.next[value^1] != nil { // 能取到1
            cur = cur | (1 << j) // 结果在该位可以为1
            temp = temp.next[value^1]
         } else {
            temp = temp.next[value]
         }
      }
      res = max(res, cur)
   }
   return res
}

type Trie struct {
   next []*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

总结

Medium题目，位运算的题目