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

题目描述：

image.png

解：

421.数组中两个数的最大异或值的进阶版
此题也是求最大的异或值，同样需要构造一个01字典树。有区别的是：

  1. 采取离线查询的方法：每次将需要参加筛选的值加入到字典树
  2. 采取在线查询的方法：一次性将数组所有值加入字典树，再对于每一个查询的值进行判断。

以下代码是抄官解的：
1.离线查询：

  1. class Solution {
  2.     public int[] maximizeXor(int[] nums, int[][] queries) {
  3.         Arrays.sort(nums);
  4.         int numQ = queries.length;
  5.         int[][] newQueries = new int[numQ][3];
  6.         for (int i = 0; i < numQ; ++i) {
  7.             newQueries[i][0] = queries[i][0];
  8.             newQueries[i][1] = queries[i][1];
  9.             newQueries[i][2] = i;
  10.         }
  11.         Arrays.sort(newQueries, new Comparator<int[]>() {
  12.             public int compare(int[] query1, int[] query2) {
  13.                 return query1[1] - query2[1];
  14.             }
  15.         });
  17.         int[] ans = new int[numQ];
  18.         Trie trie = new Trie();
  19.         int idx = 0, n = nums.length;
  20.         for (int[] query : newQueries) {
  21.             int x = query[0], m = query[1], qid = query[2];
  22.             while (idx < n && nums[idx] <= m) {
  23.                 trie.insert(nums[idx]);
  24.                 ++idx;
  25.             }
  26.             if (idx == 0) { // 字典树为空
  27.                 ans[qid] = -1;
  28.             } else {
  29.                 ans[qid] = trie.getMaxXor(x);
  30.             }
  31.         }
  32.         return ans;
  33.     }
  34. }
  36. class Trie {
  37.     static final int L = 30;
  38.     Trie[] children = new Trie[2];
  40.     public void insert(int val) {
  41.         Trie node = this;
  42.         for (int i = L - 1; i >= 0; --i) {
  43.             int bit = (val >> i) & 1;
  44.             if (node.children[bit] == null) {
  45.                 node.children[bit] = new Trie();
  46.             }
  47.             node = node.children[bit];
  48.         }
  49.     }
  51.     public int getMaxXor(int val) {
  52.         int ans = 0;
  53.         Trie node = this;
  54.         for (int i = L - 1; i >= 0; --i) {
  55.             int bit = (val >> i) & 1;
  56.             if (node.children[bit ^ 1] != null) {
  57.                 ans |= 1 << i;
  58.                 bit ^= 1;
  59.             }
  60.             node = node.children[bit];
  61.         }
  62.         return ans;
  63.     }
  64. }

2.在线查询

  1. class Solution {
  2.     public int[] maximizeXor(int[] nums, int[][] queries) {
  3.         Trie trie = new Trie();
  4.         for (int val : nums) {
  5.             trie.insert(val);
  6.         }
  7.         int numQ = queries.length;
  8.         int[] ans = new int[numQ];
  9.         for (int i = 0; i < numQ; ++i) {
  10.             ans[i] = trie.getMaxXorWithLimit(queries[i][0], queries[i][1]);
  11.         }
  12.         return ans;
  13.     }
  14. }
  16. class Trie {
  17.     static final int L = 30;
  18.     Trie[] children = new Trie[2];
  19.     int min = Integer.MAX_VALUE;
  21.     public void insert(int val) {
  22.         Trie node = this;
  23.         node.min = Math.min(node.min, val);
  24.         for (int i = L - 1; i >= 0; --i) {
  25.             int bit = (val >> i) & 1;
  26.             if (node.children[bit] == null) {
  27.                 node.children[bit] = new Trie();
  28.             }
  29.             node = node.children[bit];
  30.             node.min = Math.min(node.min, val);
  31.         }
  32.     }
  34.     public int getMaxXorWithLimit(int val, int limit) {
  35.         Trie node = this;
  36.         if (node.min > limit) {
  37.             return -1;
  38.         }
  39.         int ans = 0;
  40.         for (int i = L - 1; i >= 0; --i) {
  41.             int bit = (val >> i) & 1;
  42.             if (node.children[bit ^ 1] != null && node.children[bit ^ 1].min <= limit) {
  43.                 ans |= 1 << i;
  44.                 bit ^= 1;
  45.             }
  46.             node = node.children[bit];
  47.         }
  48.         return ans;
  49.     }
  50. }