Question

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

English Version

题目描述

给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。

第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。

返回一个整数数组_ _answer_ _作为查询的答案，其中_ _answer.length == queries.length_ _且_ _answer[i]_ _是第_ _i_ _个查询的答案。

 

示例 1：

输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

示例 2：

输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]

 

提示：

• 1 <= nums.length, queries.length <= 105
• queries[i].length == 2
• 0 <= nums[j], xi, mi <= 109

解法

方法一：离线查询 + 0-1 字典树

根据题目描述我们知道，每个查询相互独立，并且查询的结果与 $nums$ 中的元素顺序无关，因此，我们考虑将所有的查询按照 $m_i$ 从小到大排序，并且将 $nums$ 从小到大排序。

接下来，我们使用一个 $0-1$ 字典树来维护 $nums$ 中的元素。我们用一个指针 $j$ 来记录当前字典树中的元素，初始时 $j=0$。对于每个查询 $[x_i, m_i]$，我们不断地将 $nums$ 中的元素插入到字典树中，直到 $nums[j] > m_i$，此时我们就可以在字典树中查询到所有不超过 $m_i$ 的元素，我们将其中与 $x_i$ 异或值最大的元素的异或值作为答案。

时间复杂度 $O(m \times \log m + n \times (\log n + \log M))$，空间复杂度 $O(n \times \log M)$，其中 $m$ 和 $n$ 分别是数组 $nums$ 和 $queries$ 的长度，而 $M$ 是数组 $nums$ 中的最大值，本题中 $M \le 10^9$。

class Trie:
  __slots__ = ["children"]

  def __init__(self):
    self.children = [None] * 2

  def insert(self, x: int):
    node = self
    for i in range(30, -1, -1):
      v = x >> i & 1
      if node.children[v] is None:
        node.children[v] = Trie()
      node = node.children[v]

  def search(self, x: int) -> int:
    node = self
    ans = 0
    for i in range(30, -1, -1):
      v = x >> i & 1
      if node.children[v ^ 1]:
        ans |= 1 << i
        node = node.children[v ^ 1]
      elif node.children[v]:
        node = node.children[v]
      else:
        return -1
    return ans


class Solution:
  def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
    trie = Trie()
    nums.sort()
    j, n = 0, len(queries)
    ans = [-1] * n
    for i, (x, m) in sorted(zip(range(n), queries), key=lambda x: x[1][1]):
      while j < len(nums) and nums[j] <= m:
        trie.insert(nums[j])
        j += 1
      ans[i] = trie.search(x)
    return ans

class Trie {
  private Trie[] children = new Trie[2];

  public void insert(int x) {
    Trie node = this;
    for (int i = 30; i >= 0; --i) {
      int v = x >> i & 1;
      if (node.children[v] == null) {
        node.children[v] = new Trie();
      }
      node = node.children[v];
    }
  }

  public int search(int x) {
    Trie node = this;
    int ans = 0;
    for (int i = 30; i >= 0; --i) {
      int v = x >> i & 1;
      if (node.children[v ^ 1] != null) {
        ans |= 1 << i;
        node = node.children[v ^ 1];
      } else if (node.children[v] != null) {
        node = node.children[v];
      } else {
        return -1;
      }
    }
    return ans;
  }
}

class Solution {
  public int[] maximizeXor(int[] nums, int[][] queries) {
    Arrays.sort(nums);
    int n = queries.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; ++i) {
      idx[i] = i;
    }
    Arrays.sort(idx, (i, j) -> queries[i][1] - queries[j][1]);
    int[] ans = new int[n];
    Trie trie = new Trie();
    int j = 0;
    for (int i : idx) {
      int x = queries[i][0], m = queries[i][1];
      while (j < nums.length && nums[j] <= m) {
        trie.insert(nums[j++]);
      }
      ans[i] = trie.search(x);
    }
    return ans;
  }
}

class Trie {
private:
  Trie* children[2];

public:
  Trie()
    : children{nullptr, nullptr} {}

  void insert(int x) {
    Trie* node = this;
    for (int i = 30; ~i; --i) {
      int v = (x >> i) & 1;
      if (!node->children[v]) {
        node->children[v] = new Trie();
      }
      node = node->children[v];
    }
  }

  int search(int x) {
    Trie* node = this;
    int ans = 0;
    for (int i = 30; ~i; --i) {
      int v = (x >> i) & 1;
      if (node->children[v ^ 1]) {
        ans |= 1 << i;
        node = node->children[v ^ 1];
      } else if (node->children[v]) {
        node = node->children[v];
      } else {
        return -1;
      }
    }
    return ans;
  }
};

class Solution {
public:
  vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
    sort(nums.begin(), nums.end());
    int n = queries.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) { return queries[i][1] < queries[j][1]; });
    vector<int> ans(n);
    Trie trie;
    int j = 0;
    for (int i : idx) {
      int x = queries[i][0], m = queries[i][1];
      while (j < nums.size() && nums[j] <= m) {
        trie.insert(nums[j++]);
      }
      ans[i] = trie.search(x);
    }
    return ans;
  }
};

type Trie struct {
  children [2]*Trie
}

func NewTrie() *Trie {
  return &Trie{}
}

func (t *Trie) insert(x int) {
  node := t
  for i := 30; i >= 0; i-- {
    v := x >> i & 1
    if node.children[v] == nil {
      node.children[v] = NewTrie()
    }
    node = node.children[v]
  }
}

func (t *Trie) search(x int) int {
  node := t
  ans := 0
  for i := 30; i >= 0; i-- {
    v := x >> i & 1
    if node.children[v^1] != nil {
      ans |= 1 << i
      node = node.children[v^1]
    } else if node.children[v] != nil {
      node = node.children[v]
    } else {
      return -1
    }
  }
  return ans
}

func maximizeXor(nums []int, queries [][]int) []int {
  sort.Ints(nums)
  n := len(queries)
  idx := make([]int, n)
  for i := 0; i < n; i++ {
    idx[i] = i
  }
  sort.Slice(idx, func(i, j int) bool {
    return queries[idx[i]][1] < queries[idx[j]][1]
  })
  ans := make([]int, n)
  trie := NewTrie()
  j := 0
  for _, i := range idx {
    x, m := queries[i][0], queries[i][1]
    for j < len(nums) && nums[j] <= m {
      trie.insert(nums[j])
      j++
    }
    ans[i] = trie.search(x)
  }
  return ans
}

class Trie {
  children: (Trie | null)[];

  constructor() {
    this.children = [null, null];
  }

  insert(x: number): void {
    let node: Trie | null = this;
    for (let i = 30; ~i; i--) {
      const v = (x >> i) & 1;
      if (node.children[v] === null) {
        node.children[v] = new Trie();
      }
      node = node.children[v] as Trie;
    }
  }

  search(x: number): number {
    let node: Trie | null = this;
    let ans = 0;
    for (let i = 30; ~i; i--) {
      const v = (x >> i) & 1;
      if (node.children[v ^ 1] !== null) {
        ans |= 1 << i;
        node = node.children[v ^ 1] as Trie;
      } else if (node.children[v] !== null) {
        node = node.children[v] as Trie;
      } else {
        return -1;
      }
    }
    return ans;
  }
}

function maximizeXor(nums: number[], queries: number[][]): number[] {
  nums.sort((a, b) => a - b);
  const n = queries.length;
  const idx = Array.from({ length: n }, (_, i) => i);
  idx.sort((i, j) => queries[i][1] - queries[j][1]);
  const ans: number[] = [];
  const trie = new Trie();
  let j = 0;
  for (const i of idx) {
    const x = queries[i][0];
    const m = queries[i][1];
    while (j < nums.length && nums[j] <= m) {
      trie.insert(nums[j++]);
    }
    ans[i] = trie.search(x);
  }
  return ans;
}