数组中两个数的最大异或值【LC421】
Given an integer array
nums, return the maximum result ofnums[i] XOR nums[j], where0 <= i <= j < n.
字典树
- 思路
- 从字典树的根节点开始遍历，并从最高位往低位查询，优先让每一位的异或结果为1，即优先匹配与之不同的二进制位【局部最优】，这样才能使最终的异或结果最大【全局最优】，
- 实现
class Solution { class TrieNode{ TrieNode[] next = new TrieNode[2]; } TrieNode root = new TrieNode(); public int findMaximumXOR(int[] nums) { TrieNode root; int res = 0; for (int num : nums){ add(num); res = Math.max(search(num) ^ num, res); } return res; } public void add(int x){ TrieNode p = root; for (int i = 31; i >= 0; i--){ int u = (x >> i) & 1; if (p.next[u] == null) p.next[u] = new TrieNode(); p = p.next[u]; } } public int search(int x){ int res = 0; TrieNode p = root; for (int i = 31; i >= 0; i--){ int u = (x >> i) & 1, v = 1 - u; if (p.next[v] != null) { res |= (v << i); p = p.next[v]; }else { res |= (u << i); p = p.next[u]; } } return res; } }
