涉及知识点
数学 字典树
题目
给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：
|x - y| <= min(x, y)
你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。
返回数组 nums 所有可能的强数对中的 最大 异或值。
注意，你可以选择同一个整数两次来形成一个强数对。
示例 1：
输入：nums = [1,2,3,4,5]
输出：7
解释：数组 nums 中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 = 7 。
示例 2：
输入：nums = [10,100]
输出：0
解释：数组 nums 中有 2 个强数对：(10, 10) 和 (100, 100) 。
这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。
示例 3：
输入：nums = [500,520,2500,3000]
输出：1020
解释：数组 nums 中有 6 个强数对：(500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) 和 (3000, 3000) 。
这些强数对中的最大异或值是 500 XOR 520 = 1020 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 2500 XOR 3000 = 636 。
**参数范围：
1 <= nums.length <= 5 * 104
1 <= nums[i] <= 220 - 1
代码及分析
自己封装的类
class CBitTrieNode { public: CBitTrieNode* Add(bool b) { if (nullptr == m_pNode[b]) { m_pNode[b] = new CBitTrieNode(); } m_pNode[b]->m_iNum++; return m_pNode[b]; } const CBitTrieNode* Get(bool b)const { if ((nullptr != m_pNode[b])&&(m_pNode[b]->m_iNum > 0 )) { return m_pNode[b]; } return nullptr; } CBitTrieNode* SubNum(bool b) { if (nullptr == m_pNode[b]) { return nullptr; } m_pNode[b]->m_iNum–; return m_pNode[b]; } protected: int m_iNum = 0; CBitTrieNode* m_pNode[2] = { nullptr,nullptr }; }; template<class TData = int ,int iBitNum=31 > class CBitTrie { public: void Add(TData data) { CBitTrieNode* pNode = &m_root; for (int i = iBitNum - 1; i >= 0; i–) { pNode = pNode->Add(data&(1 << i)); } m_mValueNum[data]++; } void Erase(TData data) { m_mValueNum[data]–; CBitTrieNode* pNode = &m_root; for (int i = iBitNum - 1; i >= 0; i–) { pNode = pNode->SubNum(data & (1 << i)); } } CBitTrieNode m_root; protected: std::unordered_map<TData, int> m_mValueNum; };
分析
只需要考虑x<y
x,y和y,x结果完全一样。如果x等于y，其结果为0，我们将结果的初始值设置为0，就可以把重复内数据删除。
精简公式
|x - y| <= min(x, y) 因为x<y，所以 y-x <= x => y <=2x
时间复杂度
总时间复杂度：O(nlogn)。枚举x，时间复杂度O(n)。增加、删除、查询字典树，时间复杂度O(logn)。
变量解释
| m_trie | 记录所有符合条件的y：一，x < y。二，y<=2x。要做两件事：一，删除<=x的y，每次枚举x的时候，只需要删除等于x的y，小于x的y之前已经删除。二，增加新的y。 |
| iCur | x 和所有符合条件的y的最大异或和 |
如何从众多y中选择x
| 最高位是1 | 优先选择最高位为0 |
| 最高位是0 | 优先选择最高位为1 |
| 这样最高位为1 | |
| 次高为类似 | |
| … |
注意
m_trie.Erase(nums[left]); nums[left]一定符合条件，所以一定可以删除。
核心代码
class Solution { public: int maximumStrongPairXor(vector<int>& nums) { //排序并删除重复 std::sort(nums.begin(), nums.end()); nums.erase(std::unique(nums.begin(), nums.end()), nums.end()); m_c = nums.size(); int right = 0; int iRet = 0;//自已异或自己为0 for (int left = 0; left < nums.size(); left++) { //加入所有符合要求的y(nums[right]) while ((right < m_c) && (nums[left] * 2 >= nums[right])) {//是强数对 m_trie.Add(nums[right]); right++; } m_trie.Erase(nums[left]); //字典树中查询 int iCur = 0; const CBitTrieNode* ptr = &m_trie.m_root; for (int i = iBitNum-1; (nullptr != ptr) && (i >= 0); i--) { const bool b = nums[left] & (1 << i); auto tmp = ptr->Get(!b); if (nullptr != tmp) { iCur += (1 << i); ptr = tmp; continue; } ptr = ptr->Get(b); } iRet = max(iRet, iCur); } return iRet; } int m_c; static const int iBitNum = 20; CBitTrie<int, iBitNum> m_trie; };
测试用例
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector nums; int res; { nums = { 1 }; res = Solution().maximumStrongPairXor(nums); Assert(0, res); } { nums = { 1 ,2 }; res = Solution().maximumStrongPairXor(nums); Assert(3, res); } { nums = { 10 ,100 }; res = Solution().maximumStrongPairXor(nums); Assert(0, res); } { nums = { 2,2,1,1 }; res = Solution().maximumStrongPairXor(nums); Assert(3, res); } { nums = { 1 ,2, 3,4,5 }; res = Solution().maximumStrongPairXor(nums); Assert(7, res); } { nums = { 500, 520, 2500, 3000 }; res = Solution().maximumStrongPairXor(nums); Assert(1020, res); }
//CConsole::Out(res);
}
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 洒家想对大家说的话
|
|-|
|闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。|
| 墨家名称的来源：有所得以墨记之。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
