数组中xor最大的两个元素
给定一个整数数组，你必须find两个XOR最大的元素。
有一种天真的做法 – 只要挑选每个元素，然后与其他元素进行比较，然后比较结果来find这对。
除此之外，是否有任何有效的algorithm？
我想我有一个O（n lg U）algorithm，其中U是最大的数字。 这个想法类似于user949300的，但有一点细节。
直觉如下。 当你把两个数字异或时，为了得到最大值，你希望在最高位置有一个1，然后在这个位置有一个1的配对，你希望与下一个1配对可能的最高位置等
所以algorithm如下。 首先在数字的任何位置find最高的1位（通过对n个数字中的每一个进行O（lg U）工作，你可以在时间O（n lg U））做到这一点。 现在，将数组分成两部分 – 其中一个数字中有1位数字，而另一个数字中的数字是0。 任何最佳解决scheme都必须将数字与第一个数字中的1与该数字中的数字0相结合，因为这将使得1位尽可能高。 任何其他配对都有一个0。
现在，recursion地，我们想要find1和0组中具有最高1的数字的配对。 为了做到这一点，在这两个小组中，将它们分成四组：
- 以11开头的数字
- 以10开头的数字
- 以01开头的数字
- 以00开头的数字
如果在11和00组或10和01组中有任何数字，他们的异或将是理想的（从11开始）。 因此，如果这些组中的任何一组不是空的，则recursion地从这些组中计算出理想解，然后返回这些子问题解的最大值。 否则，如果两个组都是空的，这意味着所有的数字在第二个位置必须有相同的数字。 因此，从1开始的数字和从0开始的数字的最优XOR将最终取消下一个第二位，所以我们应该只看第三位。
这给出了下面的recursionalgorithm，从由MSB划分的两组数字开始，给出了答案：
- 给定组1和组0以及比特索引i：
- 如果位索引等于位数，则返回1组（唯一）号码与0组（唯一）号码的异或。
- 从这些组构build11,10,1和00组。
- 如果组11和组00不是空的，recursion地从第i + 1位开始寻找这两个组的最大XOR。
- 如果组10和组01是非空的，那么recursion地从第i + 1位开始寻找这两个组的最大异或。
- 如果上面的配对之一是可能的，则返回recursionfind的最大配对。
- 否则，所有的数字必须在位置i上具有相同的位，所以通过查看组1和0上的位i + 1返回find的最大对。
要开始执行algorithm，实际上可以将初始组中的数字划分为两组 – 数字为MSB 1，数字为MSB 0.然后用两组数字发起上述algorithm的recursion调用。
作为一个例子，考虑数字5 1 4 3 0 2。这些有代表性
101 001 100 011 000 010 我们首先将他们分成1组和0组：
101 100 001 011 000 010
现在，我们应用上面的algorithm。 我们把它分成11,10,1和00组：
11: 10: 101 100 01: 011 010 00: 000 001
现在，我们不能将任何11个元素与00个元素配对，所以我们只是对10个和01个群组进行recursion。 这意味着我们构build了100,101,010和011组：
101: 101 100: 100 011: 011 010: 010
现在我们只需要一个元素就可以了，我们可以检查101和010（它给出111）和100和011（给出111）。 这两个选项都在这里工作，所以我们得到的最佳答案是7。
我们来考虑一下这个algorithm的运行时间。 注意最大recursion深度是O（lg U），因为数字中只有O（log U）位。 在树中的每一级，每个数字只出现在一次recursion调用中，每个recursion调用的function与0和1组中的总数成正比，因为我们需要按比特分配它们。 因此，在recursion树中有O（log U）级别，每个级别都有O（n）工作，总的工作是O（n log U）。
希望这可以帮助！ 这是一个很棒的问题！
忽略符号位，其中一个值必须是具有最高有效位集的值之一。 除非所有的值都设置了这个位 ， 否则你会转到下一个没有设置在所有值中的最高有效位。 所以你可以通过查看HSB来减less第一个值的可能性。 例如，如果可能的话
0x100000 0x100ABC 0x001ABC 0x000ABC
最大对的第一个值必须是0x100000或0x10ABCD。
@内部服务器错误我不认为最小是正确的。 我没有一个好主意来削减第二个价值。 只是不在可能的第一个值列表中的任何值。 在我的例子中，0x001ABC或0x000ABC。
这可以使用Trie在O(NlogN)时间复杂度中解决。
- 构build一个trie。 对于每个整数密钥，特里的每个节点将保存从最高有效位开始的每个位（0或1）。
- 现在，对于
arr[0, 1, ..... N]每个arr[i]arr[0, 1, ..... N]- 执行查询以检索
arr[i]可能的最大异或值。 我们知道不同types的比特（0 ^ 1或1 ^ 0）的xor总是1。 所以在查询每一位的时候，试着遍历节点持有的相对位。 这将使特定的位1导致异或值最大化。 如果不存在具有相反位的节点，则只能遍历相同的位节点。 - 查询后，将
arr[i]插入到trie中。 - 对于每个元素，跟踪可能的最大Xor值。
- 在遍历每个节点的过程中，构buildXor正在被最大化的另一个键。
- 执行查询以检索
对于N元素，每个元素需要一个查询（ O(logN) ）和一个插入（ O(logN) ）。 所以总的时间复杂度是O(NlogN) 。
你可以find很好的图解说明如何在这个线程中工作 。
这里是上述algorithm的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; }
一个非常有趣的问题！ 这是我的想法：
- 首先使用二进制表示法从所有数字中构build二叉树，并将它们sorting到树中最重要的位（加上前导零以匹配最长的数字）。 完成后，从根到任何叶子的每条path代表原始集合中的一个数字。
- 让a和b指向一个树节点并在根上初始化它们。
- 现在将a和b沿着树移动，尝试在每一步使用相反的边，即如果a向下移动0边，则b向下移动1边，除非不可能。
如果a和b达到一个叶子，则应该指向具有“很less”相同位的两个数字。
我只是做了这个algorithm，不知道是否正确或如何certificate它。 但是它应该在O（n）运行时间。
创build一个recursion函数，它将两个整数列表A和B作为其参数。 作为它的返回值，它返回两个整数，一个来自A，一个来自B，这使得两者的XOR最大化。 如果所有的整数都是0，则返回（0,0）。 否则，该函数会执行一些处理，并recursion调用两次，但使用较小的整数。 在其中一个recursion调用中，它考虑从列表A中提供一个整数来提供1到位k，而在另一个调用中，它考虑从列表B中提供一个整数来提供1到位k。
我没有时间来填写细节，但也许这将足以看到答案？ 另外，我不确定运行时间是否会比N ^ 2更好，但可能会。
我们可以在O（n）时间内find最大的数字，然后循环遍历数组，对每个元素进行异或运算。 假设xor操作成本为O（1），我们可以在O（n）时间内find两个数字的最大值。
