leetcode_421数组中两个数的最大异或值

本文主要是介绍leetcode_421数组中两个数的最大异或值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题意

求数组中两个数的最大异或值

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

2. 题解

2.1 哈希表

$a_i\oplus a_j=x$
所以
$a_i=x\oplus a_j$

考虑$a_i、a_j$的每一位的所有情况

$bit(a_i,k)$	$bit(a_j,k)$	$bit(x,k)$
0	0	0
0	1	1
1	0	1
1	1	0

我们可以从最高位开始尝试，是否能使第$k$位为1。

即对$pre(k,a_j)$，$preSet(k)$中是否有$x\oplus pre(k,a_j)$使得枚举的最大前缀$x$成立。

• 代码

class Solution {
public:int findMaximumXOR(vector<int>& nums) {int ans = 0;for ( int i = 30; i > -1; --i ) {unordered_set<int> preSet;for ( int num: nums) {preSet.insert( num >> i);}ans = ans << 1 | 1;bool find = false;for (int num: nums) {if ( preSet.count( (num >> i) ^ ans )) {find = true;break;}}if ( !find)ans--;}     return ans;}
};

2.2 前缀树

可以将所有值插入到一颗0-1前缀树中，然后再遍历每个值，对于每一位尽量选择它的翻转值，如果
树中有该路径的话。最后再取最大值。

class Solution {
public:class Trie {public:Trie():isEnd(false),left(nullptr),right(nullptr){}void insert(int v) {Trie *cur = this;for ( int bit = 30; bit > -1; --bit) {int c = (1 << bit) & v;if (!c) {if (cur->left == nullptr) {cur->left = new Trie();}cur = cur->left;}else {if ( cur->right == nullptr)cur->right = new Trie();cur = cur->right;}}cur->isEnd = true;}int getMaxXor(int v) {int ans = 0;Trie *cur = this;for ( int bit = 30; bit > -1; --bit) {int c = (1 << bit) & v;if (c) {if ( cur->left) {cur = cur->left;ans |= (1 << bit);}else {cur = cur->right;}}else {if ( cur->right ) {cur  = cur->right;ans |= (1 << bit);}else {cur = cur->left;}}}return ans; }private:Trie *left;Trie *right;bool isEnd;};int findMaximumXOR(vector<int>& nums) {Trie trie;for (int num: nums)trie.insert(num);int ans = 0;for (int num:nums) {ans = max(ans, trie.getMaxXor(num) );}return ans;}
};

这篇关于leetcode_421数组中两个数的最大异或值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---