[leetcode] 421. Maximum XOR of Two Numbers in an Array

[leetcode] 421. Maximum XOR of Two Numbers in an Array

Description

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 2^31.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]Output: 28Explanation: The maximum result is 5 ^ 25 = 28.

分析

题目的意思是：找出一个数组中两个数的最大异或值。

利用了异或的”自反性“： a ^ b = c，而a ^ b ^ b = a, 则 c ^ b = a计算使用的结果，不是只看一位，而是每次把新的一位加到原来的结果后面。这样的好处是不需要记录之前的结果满足条件的有哪些，每次就重新计算和查找就可以了，大大降低了复杂度。

看上面的例子： 我们希望用二进制来拼出结果的数，最终结果28的二进制数为11100，里面有三个‘1’，我们来找一下都是谁贡献了这三个‘1’？在 i=4 时，数字25贡献了最高位的‘1’，在 i=3 时，数字25贡献了次高位的‘1’，在 i=2 时，数字5贡献了第三位的‘1’。而一旦某个数贡献了‘1’，那么之后在需要贡献‘1’的时候，此数就可以再继续贡献‘1’。而一旦有两个数贡献了‘1’后，那么之后的‘1’就基本上只跟这两个数有关了，其他数字有‘1’也贡献不出来。

代码

class Solution {public: int findMaximumXOR(vector& nums) { int res=0; int mask=0; // from left to right for(int i=31;i>=0;i--){ mask|=(1< s; for(int num:nums){ s.insert(num&mask); } int t=res|(1<

参考文献

​​[LeetCode] Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字​​​​【特别好】【位运算】maximum-xor-of-two-numbers-in-an-array​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。