C++字典树算法：找出强数对的最大异或值 II

涉及知识点

数学字典树

题目

给你一个下标从 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);
}