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

Every day a Leetcode

题目来源：421. 数组中两个数的最大异或值

解法1：贪心 + 位运算

1. 初始化答案 ans = 0。
2. 从最高位 high_bit 开始枚举 i，也就是 max⁡(nums) 的二进制长度减一。
3. 设 newAns = ans + 2ⁱ，看能否从数组 nums 中选两个数（低于 i 的比特位当作 000），满足这两个数的异或和等于 newAns。如果可以，则更新 ans 为 newAns，否则 ans 保持不变。

代码：

/** @lc app=leetcode.cn id=421 lang=cpp** [421] 数组中两个数的最大异或值*/// @lc code=start
class Solution
{
public:int findMaximumXOR(vector<int> &nums){int mx = *max_element(nums.begin(), nums.end());int high_bit = mx ? 31 - __builtin_clz(mx) : -1;int ans = 0, mask = 0;unordered_set<int> seen;// 从最高位开始枚举for (int i = high_bit; i >= 0; i--){seen.clear();mask |= 1 << i;int new_ans = ans | (1 << i); // 这个比特位可以是 1 吗？for (int x : nums){x &= mask; // 低于 i 的比特位置为 0if (seen.contains(new_ans ^ x)){ans = new_ans; // 这个比特位可以是 1break;}seen.insert(x);}}return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(nlog⁡U)，其中 n 为 nums 的长度，U=max⁡(nums)。外层循环需要循环 O(logU) 次。

空间复杂度：O(n)。哈希表中至多有 n 个数。