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

# 题目

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

[https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/](https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/)

给你一个由非负整数组成的数组 `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`

# 题解

## 思路

暴力超时，加map记表会内存溢出

## 代码

```javascript
/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
var maximizeXor = function(nums, queries) {
    const ans = [];
    let sum;
    let index;
    let tmp;
    let key;
    nums.sort((a, b) => a - b);
    // let map = new Map();
    for(let query of queries){
        sum = 0;
        for(index = 0; nums[index] <= query[1]; index++) {
            // key = query[0] > nums[index] ? `${nums[index]},${query[0]}` : `${query[0]},${nums[index]}`;
            // tmp = map.get(key);
            // if (!tmp) {
            //     tmp = query[0] ^ nums[index];
            //     map.set(key, tmp);
            // }
            // sum = Math.max(sum, tmp);
            sum = Math.max(sum, query[0] ^ nums[index]);
        }
        ans.push(index === 0 ? -1 : sum);
    }
    return ans;
};
```

## 官方

```javascript
/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
function PrefixTree(val){
    // 使用对象作为存储结构内存会溢出
    return [val,null,null]
}
PrefixTree.prototype = Object.create(null);
function getMax(val,maxDigit,node){
    let ans = 0;
    for( let j = maxDigit - 1 ; j >= 0; j--){
        let key = ((val >> j) & 1) + 1;
        // key = 2 期望 1 1期望2  尽量获取当前路径的最大值
        if( node[3-key] ){
            ans = 2* ans + 1;
            node = node[3-key]
        }else{
            ans = 2* ans;
            node = node[key]
        }
    }
    // 右移超过当前nums中的最大位的位数后还有剩余 说明val也就是xi的值要比nums[i]中的最大值大
    // 最后的结果需要加上 
    
    if( (val >> (maxDigit - 1)) > 1 ){
        ans += (val >> maxDigit) * (2 << (maxDigit - 1))
    }
    return ans;
}
var maximizeXor = function(nums, queries) {

var max = 0;
    var numsL = nums.length;
    var queriesL = queries.length;

nums.sort( (a,b) => {
        max = Math.max(max,a,b)
        return  ( a - b)
    })

if( numsL === 1 ){
        max = nums[0]
    }

var maxBinDigit = 0;
    while(max){
        maxBinDigit++;
        max >>= 1;
    };

for( let i = 0 ; i < queriesL; i++ ){
        queries[i].push(i)
    }

queries.sort((a,b) => {
        return a[1] - b[1]
    })

暴力，似乎只有js可以

```javascript
/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
var maximizeXor = function (nums, queries) {
    nums.sort((a, b) => a - b)
    return queries.map(q => {
        let m = -1
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] > q[1]) break
            if (m < (nums[i] ^ q[0])) m = nums[i] ^ q[0]
        }
        return m
    })
};
```