2023-11-04每日一题

一、题目编号

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

二、题目链接

点击跳转到题目位置

三、题目描述

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

示例 1：

示例 2：

提示：

• 1 <= nums.length <= 2 * 10⁵
• 0 <= nums[i] <= 2³¹ - 1

四、解题代码

class Solution {
private:// 最高位的二进制位编号为 30static constexpr int HIGH_BIT = 30;public:int findMaximumXOR(vector<int>& nums) {int x = 0;for (int k = HIGH_BIT; k >= 0; --k) {unordered_set<int> seen;// 将所有的 pre^k(a_j) 放入哈希表中for (int num: nums) {// 如果只想保留从最高位开始到第 k 个二进制位为止的部分// 只需将其右移 k 位seen.insert(num >> k);}// 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分// 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1int x_next = x * 2 + 1;bool found = false;// 枚举 ifor (int num: nums) {if (seen.count(x_next ^ (num >> k))) {found = true;break;}}if (found) {x = x_next;}else {// 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0// 即为 x = x*2x = x_next - 1;}}return x;}
};

五、解题思路

(1) 哈希表