421.数组中两个数的最大异或值

链接：421.数组中两个数的最大异或值
难度：Medium
标签：位运算、字典树、数组、哈希表
简介：给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

题解 1 - typescript

• 编辑时间：2021-05-16
• 执行用时：6480ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：O(n2)循环。

function findMaximumXOR(nums: number[]): number {
  let ans = -Infinity;
  nums.forEach(v1 => nums.forEach(v2 => (ans = Math.max(ans, v1 ^ v2))));
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-05-16
• 执行用时：156ms
• 内存消耗：49.2MB
• 编程语言：typescript
• 解法介绍：利用 trie 储存二进制，每次寻找尽可能大的数。

class Trie {
  /** 左 0  */
  left: Trie | null = null;
  /** 右 1  */
  right: Trie | null = null;
}
function findMaximumXOR(nums: number[]): number {
  const len = nums.length;
  if (len === 1) return 0;
  const root = new Trie();
  let ans = -Infinity;
  const add = (num: number) => {
    let trie = root;
    for (let i = 30; i >= 0; i--) {
      const v = (num >> i) & 1;
      if (v === 1) {
        trie = trie.right ?? (trie.right = new Trie());
      } else {
        trie = trie.left ?? (trie.left = new Trie());
      }
    }
  };
  const check = (num: number): number => {
    let trie = root;
    let xorNum = 0;
    for (let i = 30; i >= 0; i--) {
      const v = (num >> i) & 1;
      if (v === 1) {
        if (trie.left) {
          trie = trie.left;
          xorNum = (xorNum << 1) + 1;
        } else {
          trie = trie.right!;
          xorNum <<= 1;
        }
      } else {
        if (trie.right) {
          trie = trie.right;
          xorNum = (xorNum << 1) + 1;
        } else {
          trie = trie.left!;
          xorNum <<= 1;
        }
      }
    }
    return xorNum;
  };
  for (let i = 1; i < len; i++) {
    add(nums[i - 1]);
    ans = Math.max(ans, check(nums[i]));
  }
  return ans;
}

题解 3 - typescript

• 编辑时间：2021-10-25
• 执行用时：788ms
• 内存消耗：67.5MB
• 编程语言：typescript
• 解法介绍：二叉字典树。

const MAX = 31;
class BitTrieNode {
  // 0
  left: BitTrieNode | null = null;
  // 1
  right: BitTrieNode | null = null;
  val = -1;
}
class BitTrie {
  root = new BitTrieNode();
  add(num: number) {
    const str = num.toString(2).padStart(MAX, '0');
    let node = this.root;
    for (let i = 0, l = str.length; i < l; i++) {
      const ch = str[i];
      if (ch === '0') node = node.left ?? (node.left = new BitTrieNode());
      else node = node.right ?? (node.right = new BitTrieNode());
    }
    node.val = num;
  }
  find(num: number) {
    const str = num.toString(2).padStart(MAX, '0');
    let node = this.root;
    for (let i = 0, l = str.length; i < l; i++) {
      if (!node.left && !node.right) break;
      const ch = str[i];
      if (ch === '0') {
        node = node.right ?? node.left!;
      } else {
        node = node.left ?? node.right!;
      }
    }
    return node;
  }
}
function findMaximumXOR(nums: number[]): number {
  const trie = new BitTrie();
  nums.forEach(num => trie.add(num));
  let ans = -Infinity;
  nums.forEach(num => {
    ans = Math.max(ans, trie.find(num).val ^ num);
  });
  return ans;
}

题解 4 - cpp

• 编辑时间：2023-11-04
• 执行用时：716ms
• 内存消耗：172.36MB
• 编程语言：cpp
• 解法介绍：同上。

struct TrieNode {
    TrieNode* left = nullptr;
    TrieNode* right = nullptr;
};
void add(TrieNode* node, int num) {
    int pos = 30;
    while (pos >= 0) {
        int v = (num >> pos) & 1;
        if (v) {
            if (!node->left) node->left = new TrieNode();
            node = node->left;
        } else {
            if (!node->right) node->right = new TrieNode();
            node = node->right;
        }
        pos -= 1;
    }
}
int find(TrieNode* node, int num) {
    int pos = 30, ans = 0;
    while (pos >= 0 && node) {
        int v = (num >> pos) & 1;
        if (v) {
            if (node->right) {
                ans |= 1 << pos;
                node = node->right;
            } else node = node->left;
        } else {
            if (node->left) {
                ans |= 1 << pos;
                node = node->left;
            } else node = node->right;
        }
        pos -= 1;
    }
    return ans;
}
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        TrieNode *root = new TrieNode();
        int ans = 0;
        for (auto &num : nums) {
            add(root, num);
            ans = max(ans, find(root, num));
        }
        return ans;
    }
};

题解 5 - python

• 编辑时间：2023-11-04
• 执行用时：9296ms
• 内存消耗：444.3MB
• 编程语言：python
• 解法介绍：同上。

class TrieNode:
    def __init__(self):
        self.left = self.right = None
    
def add(node, num: int, pos: int):
    while pos >= 0:
        v = (num >> pos) & 1
        if v:
            if not node.left: node.left = TrieNode()
            node = node.left
        else:
            if not node.right: node.right = TrieNode()
            node = node.right
        pos -= 1
        
def find(node, num: int, pos: int):
    ans = 0
    while pos >= 0 and node:
        v = (num >> pos) & 1
        if v: 
            if node.right:
                ans |= 1 << pos
                node = node.right
            else:
                node = node.left
        else:
            if node.left:
                ans |= 1 << pos
                node = node.left
            else:
                node = node.right
        pos -= 1
    return ans
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        root = TrieNode()
        ans = 0
        for num in nums: 
            add(root, num, 30)
            ans = max(ans, find(root, num, 30))
        return ans

题解 6 - rust

• 编辑时间：2023-11-04
• 执行用时：564ms
• 内存消耗：85MB
• 编程语言：rust
• 解法介绍：同上。

struct TrieNode {
    left: Option<Box<TrieNode>>,
    right: Option<Box<TrieNode>>,
}
impl TrieNode {
    fn new() -> Self {
        Self {
            left: None,
            right: None,
        }
    }
}
fn add(mut node: &mut Box<TrieNode>, num: i32) {
    let mut pos = 30;
    while pos >= 0 {
        let v = (num >> pos) & 1;
        if v != 0 {
            if node.left.is_none() {
                node.left = Some(Box::new(TrieNode::new()));
            }
            node = node.left.as_mut().unwrap()
        } else {
            if node.right.is_none() {
                node.right = Some(Box::new(TrieNode::new()));
            }
            node = node.right.as_mut().unwrap()
        }
        pos -= 1;
    }
}
fn find(mut node: &Box<TrieNode>, num: i32) -> i32 {
    let mut pos = 30;
    let mut ans = 0;
    let mut node = Some(node);
    while pos >= 0 && node.is_some() {
        let node_ref = node.unwrap();
        let v = (num >> pos) & 1;
        if v != 0 {
            if node_ref.right.is_some() {
                ans |= 1 << pos;
                node = Some(node_ref.right.as_ref().unwrap());
            } else if node_ref.left.is_some() {
                node = Some(node_ref.left.as_ref().unwrap());
            } else {
                node = None;
            }
        } else {
            if node_ref.left.is_some() {
                ans |= 1 << pos;
                node = Some(node_ref.left.as_ref().unwrap());
            } else if node_ref.right.is_some() {
                node = Some(node_ref.right.as_ref().unwrap());
            } else {
                node = None;
            }
        }
        pos -= 1;
    }
    ans
}
impl Solution {
    pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
        let mut root = Box::new(TrieNode::new());
        let mut ans = 0;
        for num in &nums {
            add(&mut root, *num);
        }
        for num in &nums {
            ans = ans.max(find(&root, *num));
        }
        ans
    }
}