给定一个整数数组，需要找到两个元素的异或值最大。
一种朴素的方法是选择每个元素并将其与其他元素进行异或，然后比较结果以找到这对元素。
除此之外，是否有更有效的算法？
数组中两个元素的异或值最大是多少？
54
- Anil Arya
4
一个好的选择是取最大值和最小值，因为小值的位在进行异或运算时不太可能“破坏”高值的“好”的高位。 - 500 - Internal Server Error
5arr={8,4,2} 失败，答案是 8^4，4 不是最小值... - Anil Arya
1@500-服务器内部错误：它肯定是一对数字，其中一个数字的最高位被设置，另一个数字的最高位被重置。 - Alexey Frunze
重复元素是否允许存在，或者所有整数都是唯一的？ - Alexey Frunze
6个回答
49
我认为我有一个时间复杂度为
直觉如下。当你将两个数字进行异或运算时，为了获得最大值，你希望在可能的最高位上有一个
因此，该算法如下。首先找到任何数字中最高的
现在，递归地，我们要找到来自具有最高
- 以
如果在
这给出了以下递归算法，在从其 MSB 分区的两个数字组开始之后，会得到答案：
- 给定分组
O(n lg U) 的算法，其中 U 是最大的数字。这个想法与 user949300 的类似，但具体细节更多一些。直觉如下。当你将两个数字进行异或运算时，为了获得最大值，你希望在可能的最高位上有一个
1，并且在拥有此位上的 1 的配对中，您希望选择下一个最高位上有 1 的配对等等。因此，该算法如下。首先找到任何数字中最高的
1 位（通过对每个数字执行 O(lg U) 工作来完成，总共需要 O(n lg U) 时间）。现在，将数组分成两部分 - 其中一部分是在该位上有 1 的数字，而另一组则为在该位上为 0 的数字。任何最优解都必须组合一个在第一位上有 1 的数字和一个在该处为 0 的数字，因为这会将一个 1 位放置得尽可能高。任何其他配对都会在那里有一个 0。现在，递归地，我们要找到来自具有最高
1 的数字的 1 和 0 组的配对。为此，将它们中的两个组分成四个组：- 以
11 开头的数字
- 以 10 开头的数字
- 以 01 开头的数字
- 以 00 开头的数字如果在
11 和 00 组或 10 和 01 组中有任何数字，则它们的异或结果将是理想的（从 11 开始）。因此，如果这些组中的任意一对不为空，则递归计算这些组的理想解决方案，然后返回这些子问题解决方案的最大值。否则，如果两个组都为空，这意味着所有数字的第二位数字必须相同。因此，一个以 1 开头的数字和一个以 0 开头的数字的最佳异或将导致下一个第二位取消，因此我们只需查看第三位即可。这给出了以下递归算法，在从其 MSB 分区的两个数字组开始之后，会得到答案：
- 给定分组
1 和分组 0 以及位索引 i：
- 如果位索引等于位数，则返回在 1 组中的（唯一）数字与在 0 组中的（唯一）数字的异或结果。
- 从这些组构建组 11、10、01 和 00。
- 如果组 11 和组 00 非空，则递归找到从第 i+1 位开始的那两个组的最大异或值。
- 如果组 10 和组 01 非空，则递归查找这两个组的最大异或值，从第 i+1 位开始。
- 如果上述任何101 001 100 011 000 010
我们首先把它们分成1组和0组：
101 100
001 011 000 010
现在，我们应用上述算法。我们将其分为组11、10、01和00:
11:
10: 101 100
01: 011 010
00: 000 001
现在，我们无法将任何11元素与00元素配对，因此我们只需对10和01组进行递归。这意味着我们构造了100、101、010和011组：
101: 101
100: 100
011: 011
010: 010
- templatetypedef
7
1我也考虑过查看多个位（11 vs. 10），我的直觉是，在那时，可能更快的方法是直接穿过所有组合。而且我也不想那么辛苦地思考并修复所有可能出现的错误 :-) 当然，这取决于N的大小，对于巨大的N，你的方法会更快。 - user949300
你说数字中有O(log U)位是什么意思？根据定义，存在一个具有U位的数字，因此是O(U)。我认为你的运行时间至少是O(NU)。 - David Grayson
1你假设具有最高相关位位置的数字集合是非空的。此外，我不相信您可以在O(log(U))时间内确定U位数字中设置的最高位。 - Chris Hopman
哦，我看到了log(U)的问题所在。是你的第一行代码...应该是“U是数字的上限”，而不是“U是最大数字中的位数”。log(U)是位数，而不是U。 - Chris Hopman
1该算法对以下情况失败：[4,6,7]；[8,10,2]；[14,15,9,3,2]和[15,15,9,3,2]。请查看此分析以及该算法的修复版本：https://discuss.leetcode.com/topic/64431/a-solution-based-on-bartoszkp-s-with-missing-test-cases。 - BartoszKP
显示剩余2条评论
7
可以使用Trie在 O(NlogN) 时间复杂度内解决此问题。
- 构造一个Trie，对于每个整数键，Trie的每个节点都将保存从最高有效位开始的每个0或1位。
- 对于
arr[0,1,.....N]的每个arr[i]元素- 执行查询以检索
arr[i]可能的最大异或值。我们知道不同类型的位（0 ^ 1或1 ^ 0）的异或始终是1。因此，在查询每个位时，请尝试遍历持有相反位的节点。这将使特定位1的结果最大化Xor值。如果没有相反位的节点，则仅遍历相同位节点。 - 查询后，将
arr[i]插入Trie中。 - 对于每个元素，跟踪可能的最大Xor值。
- 在遍历每个节点时，构建其他键，使Xor最大化。
- 执行查询以检索
对于N个元素，我们需要为每个元素进行一次查询(O(logN))和一次插入(O(logN))。因此，总时间复杂度为O(NlogN)。
您可以在此线程中找到关于它如何工作的精美图解。
以下是上述算法的C++实现：
const static int SIZE = 2;
const static int MSB = 30;
class trie {
private:
struct trieNode {
trieNode* children[SIZE];
trieNode() {
for(int i = 0; i < SIZE; ++i) {
children[i] = nullptr;
}
}
~trieNode() {
for(int i = 0; i < SIZE; ++i) {
delete children[i];
children[i] = nullptr;
}
}
};
trieNode* root;
public:
trie(): root(new trieNode()) {
}
~trie() {
delete root;
root = nullptr;
}
void insert(int key) {
trieNode* pCrawl = root;
for(int i = MSB; i >= 0; --i) {
bool bit = (bool)(key & (1 << i));
if(!pCrawl->children[bit]) {
pCrawl->children[bit] = new trieNode();
}
pCrawl = pCrawl->children[bit];
}
}
int query(int key, int& otherKey) {
int Xor = 0;
trieNode *pCrawl = root;
for(int i = MSB; i >= 0; --i) {
bool bit = (bool)(key & (1 << i));
if(pCrawl->children[!bit]) {
pCrawl = pCrawl->children[!bit];
Xor |= (1 << i);
if(!bit) {
otherKey |= (1 << i);
} else {
otherKey &= ~(1 << i);
}
} else {
if(bit) {
otherKey |= (1 << i);
} else {
otherKey &= ~(1 << i);
}
pCrawl = pCrawl->children[bit];
}
}
return Xor;
}
};
pair<int, int> findMaximumXorElements(vector<int>& arr) {
int n = arr.size();
int maxXor = 0;
pair<int, int> result;
if(n < 2) return result;
trie* Trie = new trie();
Trie->insert(0); // insert 0 initially otherwise first query won't find node to traverse
for(int i = 0; i < n; i++) {
int elem = 0;
int curr = Trie->query(arr[i], elem);
if(curr > maxXor) {
maxXor = curr;
result = {arr[i], elem};
}
Trie->insert(arr[i]);
}
delete Trie;
return result;
}
- Kaidul
1
太棒了！我发现你的答案是这个帖子中最容易理解的。我有一个问题，提前道歉因为我要顶一下老贴：对数部分从哪里来？我的意思是，对于数组中的每个元素，我们执行插入和查询，每个操作都需要恰好
C步（整数编码的宽度，在我们的例子中为32），所以我们的复杂度不应该像插入需要N * C步加上查询需要N * C步，结果为O(2 * (N * C)) <=> O(N)吗？ - DVNO5
忽略符号位，其中一个值必须是具有最高有效位设置的值之一。 除非所有的值都设置了该位，在这种情况下，您需要查找所有值中未设置的下一个最高有效位。因此，您可以通过查看HSB来减少第一个值的可能性。例如，如果可能性为
0x100000
0x100ABC
0x001ABC
0x000ABC
最大对的第一个值必须是0x100000或0x10ABCD中的一个。
@internal Server Error 我认为最小值不一定正确。我没有很好的想法来缩小第二个值。只需选择任何不在可能的第一个值列表中的值即可。 在我的示例中，可以选择0x001ABC或0x000ABC。
- user949300
4
一个非常有趣的问题！
我的想法是：
- 首先，通过使用二进制表示法从所有数字中构建二叉树，并按最高有效位排序（添加前导零以匹配最长数字）。完成后，从根到任何叶子的每个路径都代表原始集合中的一个数字。
- 让a和b成为指向树节点的指针，并将它们初始化为根。
- 现在，将a和b向下移动树，每步尝试使用相反的边，即如果a向下移动0边，则b向下移动1边，除非不可能。
如果a和b到达叶子，它们应该指向两个具有“非常少”相同位的数字。
我刚刚想出了这个算法，不知道它是否正确或如何证明它。但是它应该在O(n)运行时间内完成。
- NiklasMM
5
我喜欢制作树的想法，但如果A和B都可以到达0或1节点，你该怎么办？我认为你必须尝试两种可能性来确定哪个更好。 - David Grayson
我认为这不是一个问题，因为A和B是无法区分的，即A -> 1，B -> 0和A -> 0，B -> 1实际上是同一种情况，对吗？ - NiklasMM
是的，一旦您超越了第一步，A和B就在树中的不同位置，因此移动到哪个位置会有所区别。您正在正确的轨道上，但只需要更多的复杂性。 - David Grayson
实际上，复杂度是O(n * log(U))，其中U是给定数字中最大的数，类似于templatetypedef的答案。 - sk1pro99
@DavidGrayson 请看一下。这是你解决方案的一个实现表单。https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/795098/C-16ms-runtime-O(n)-solution-beats-100-of-submissions - Abhay Patil
1
编写一个递归函数，它以两个整数列表A和B作为参数。作为其返回值，它返回两个整数，一个来自A，另一个来自B，它们的异或值最大。如果所有整数都是0，则返回(0,0)。否则，该函数进行一些处理，并递归调用自身两次，但使用较小的整数。在其中一个递归调用中，它考虑从列表A中取一个整数来提供1到位k，而在另一个调用中，它考虑从列表B中取一个整数来提供1到位k。
我现在没有时间填写细节，但也许这就足够看到答案了？此外，我不确定运行时间是否比N^2更好，但可能会更好。
我现在没有时间填写细节，但也许这就足够看到答案了？此外，我不确定运行时间是否比N^2更好，但可能会更好。
- David Grayson
-3
我们可以在O(n)时间内找到最大的数字，然后循环遍历数组并与每个元素进行异或运算。假设异或操作的成本为O(1)，则我们可以在O(n)时间内找到两个数字的最大异或值。
- user4131265
1
1我很好奇您如何证明最大的数字必须是具有最大异或结果的一对数字之一。我确信这是不正确的。 - René Vogt
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接