方法一:哈希表
1. 如何判断 x 的k位是否能取到 1,我们先将数组前k+1位保存到集合seen中。
2. 假设x 包含从最高位开始到第 k+1 个二进制位为止的部分,则前k位为 xNext = x*2+1。 3. 枚举nums,查询集合seen中是否存在 xNext ^(num>>i)。
var findMaximumXOR = function(nums) { const HIGH_BIT = 30; let x = 0; for(let i=HIGH_BIT;i>=0;i--){ let seen = new Set(); for(let num of nums){ seen.add(num>>i); } let xNext = 2*x+1; let found = false; for(let num of nums){ if(seen.has(xNext^(num>>i))){ found = true; break; } } if(found){ x = xNext; }else{ x = xNext - 1; } } return x; } let nums = [3,10,5,25,2,8] console.log(nums, findMaximumXOR(nums)); nums = [0] console.log(nums, findMaximumXOR(nums)); nums = [2,4] console.log(nums, findMaximumXOR(nums)); nums = [8,10,2] console.log(nums, findMaximumXOR(nums)); nums = [14,70,53,83,49,91,36,80,92,51,66,70] console.log(nums, findMaximumXOR(nums));
方法二: Trie树,左子树为0, 右子树为1
var findMaximumXOR = function(nums) { //因为0 <= nums[i] <= 231 - 1,所以可以通过获取最大数的二进制位数缩小Trie树层数。 const HIGH_BIT = Math.max(...nums).toString(2).length; let n = nums.length; class bitTrie { constructor(){ this.root = this.Trie(); } Trie(){ let obj = new Object(); obj.left = null; obj.right = null; return obj; } add(num){ let cur = this.root; for(let i=HIGH_BIT;i>=0;i--){ let bit = (num>>i)&1; if(bit === 0){ if(!cur.left){ cur.left = this.Trie(); } cur = cur.left; }else{ if(!cur.right){ cur.right = this.Trie(); } cur = cur.right; } } } check(num){ let cur = this.root; let x = 0; for(let i = HIGH_BIT;i>=0;i--){ let bit = (num>>i)&1; if(bit === 0){ if(cur.right){ cur = cur.right; x=2*x+1; }else{ cur = cur.left; x=2*x; } }else{ if(cur.left){ cur = cur.left; x=2*x+1; }else{ cur = cur.right; x=2*x; } } } return x; } } let root = new bitTrie(); let x = 0; for(let i = 1;i<n;i++){ root.add(nums[i-1]); x = Math.max(x, root.check(nums[i])); } return x; }
提示:
1 <= nums.length <= 2 * 104 0 <= nums[i] <= 231 - 1