1707.与数组中元素的最大异或值

链接：1707.与数组中元素的最大异或值
难度：Hard
标签：位运算、字典树、数组
简介：返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。

题解 1 - typescript

• 编辑时间：2021-05-23
• 执行用时：3000ms
• 内存消耗：122.9MB
• 编程语言：typescript
• 解法介绍：构建字典树，排序后计算最大可能异或值。

class Trie {
  left: Trie | null = null;
  right: Trie | null = null;
  val: number | null = null;
}
function maximizeXor(nums: number[], queries: number[][]): number[] {
  const root = new Trie();
  const add = (num: number) => {
    let node = root;
    for (let i = 31; i >= 0; i--) {
      const val = (num >> i) & 1;
      if (val === 1) node = node.right ?? (node.right = new Trie());
      else node = node.left ?? (node.left = new Trie());
      node.val = num;
    }
  };
  const select = (num: number): number => {
    let node = root;
    for (let i = 31; i >= 0; i--) {
      const val = (num >> i) & 1;
      if (val === 1) node = node.left ?? node.right!;
      else node = node.right ?? node.left!;
    }
    return node.val!;
  };
  nums.sort((a, b) => a - b);
  const queryMap = new Map<number[], number>();
  queries.forEach((v, i) => queryMap.set(v, i));
  queries.sort(([, a], [, b]) => a - b);
  const ans: number[] = [];
  for (const query of queries) {
    const [x, m] = query;
    while (nums.length > 0 && nums[0] <= m) add(nums.shift()!);
    const index = queryMap.get(query)!;
    ans[index] = root.left === null && root.right === null ? -1 : x ^ select(x);
  }
  return ans;
}