[421] 数组中两个数的最大异或值

## [421] 数组中两个数的最大异或值

[力扣原题链接](https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/)

给你一个整数数组 `nums` ，返回 `nums[i] XOR nums[j]` 的最大运算结果，其中 `0 ≤ i ≤ j < n` 。

进阶：你可以在 `O(n)` 的时间解决这个问题吗？

**示例 1:**

<pre class="prettyprint linenums prettyprinted"><ol class="linenums"><li class="L0"><code> 输入：nums = [3,10,5,25,2,8]</code></li><li class="L1" data-node-id="20210516220557-mbyftgx"><code> 输出：28</code></li><li class="L2"><code> 解释：最大运算结果是 5 XOR 25 = 28.</code></li></ol></pre>

**示例 2:**

**示例 3:**

**示例 4:**

**示例 5:**

**提示：**

* `1 <= nums.length <= 2 * 104`
* `0 <= nums[i] <= 231 - 1`

### 题解

暴力的二重遍历可以解答，但是会超出时间显示。力扣的题解都是通过二进制实现，看不懂，放弃。查了另外大佬的题解发现看懂的方法，利用剪枝的方法减少时间复杂度。原理是:两数异或的最大值不会超过两个数相加,但是这种方法如果都是统一数据的情况，时间复杂度依旧是 O(N*N)
[大佬题解链接](https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/c-pai-xu-jia-jian-zhi-jian-dan-shi-xian-qj8su/)
[力扣题解](https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/shu-zu-zhong-liang-ge-shu-de-zui-da-yi-h-n9m9/)

### 代码

```cpp
class Solution {
public:
 int findMaximumXOR(vector<int>& nums) {
 sort(nums.begin(), nums.end());
 int n = nums.size();
 long long maxValue = 0;
 for (int i = n -1; i >= 1; i--) {
 for (int j = i -1; j >= 0; j--) {
 if ((long long)(nums[i]) + nums[j] < maxValue) {
 break;
 }
 maxValue = max(maxValue, (long long)(nums[i] ^ nums[j]));
 }
 }
 return maxValue;

}
};
```