https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
X.O(32N) + prefix
http://www.voidcn.com/article/p-zsinbvxx-hk.html
此解法时间复杂度为
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91049/Java-O(n)-solution-using-bit-manipulation-and-HashMap
When I tried to solve this problem, I quickly came up with the idea that we should build the answer bit by bit from the most significant bit. For any bit, it's easy to see if it can be built from all the numbers(just test whether there exist a 0 and 1 for that bit), but I had the difficulty to make sure that we're only using two numbers to do the build. The '''set.contains(tmp^prefix)''' solve my problem, we don't need to remember which two numbers we used to get the previous bit, we just need to test whether a new candidate(tmp), can be built, and make sure that its built by using two numbers
http://www.cnblogs.com/grandyang/p/5991530.html
按位遍历，题目中给定了数字的返回不会超过231,那么最多只能有32位，我们用一个从左往右的mask，用来提取数字的前缀，然后将其都存入set中，我们用一个变量t，用来验证当前位为1再或上之前结果res，看结果和set中的前缀异或之后在不在set中，这里用到了一个性质，若a^b=c，那么a=b^c，因为t是我们要验证的当前最大值，所以我们遍历set中的数时，和t异或后的结果仍在set中，说明两个前缀可以异或出t的值，所以我们更新res为t，继续遍历，如果上述讲解不容易理解，那么建议自己带个例子一步一步试试，并把每次循环中set中所有的数字都打印出来，基本应该就能理解了
http://blog.csdn.net/mebiuw/article/details/52901057
不过两个解法的核心都是：
a^b = c ->a^c=b,b^c=a
// a^b = c ->a^c=b,b^c=a public int findMaximumXOR(int[] nums) { int max = 0, mask = 0; for(int i = 31; i >= 0; i--){ //mask从0x01 ->0x03等一直变化，取后i位 mask = mask | (1 << i); Set<Integer> set = new HashSet<>(); for(int num : nums){ set.add(num & mask); } //tmp表示当前的最大 int tmp = max | (1 << i); System.out.println(mask+" "+tmp+" "+max); for(int prefix : set){ //证明存在一个数使得tmp^x = prefix if(set.contains(tmp ^ prefix)) { max = tmp; break; } } } return max; }
https://segmentfault.com/a/1190000007283296
X.
解法II Set数据结构 + 位运算
https://discuss.leetcode.com/topic/63299/python-6-lines-bit-by-bit/2
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
Insert + Query at same time
X.
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/184434/JavaTrie99
http://hankerzheng.com/blog/LeetCode-Maximum-XOR-of-Two-Numbers-in-an-Array
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91124/Java-bit-manipulation-and-divide-into-two-groups.
TODO
https://discuss.leetcode.com/topic/64431/a-solution-based-on-bartoszkp-s-with-missing-test-cases
https://discuss.leetcode.com/topic/63759/c-o-nlogk-solution-with-ordering-bits-with-o-logk-additional-memory-for-recursion-stack
http://www.1point3acres.com/bbs/thread-202685-3-1.html
Related:
https://www.geeksforgeeks.org/minimum-xor-value-pair/
Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32. Find the maximum result of a[i] XOR a[j].
Could you do this in O(n) runtime?
Input: [3, 10, 5, 25, 2, 8]
Output: 28
Output: 28
X.O(32N) + prefix
http://www.voidcn.com/article/p-zsinbvxx-hk.html
public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
// search from left to right, find out for each bit is there
// two numbers that has different value
for(int i = 31; i >= 0; i--){
// mask contains the bits considered so far
mask = mask | (1 << i);
Set<Integer> set = new HashSet<>();
// store prefix of all number with right i bits discarded
for(int num : nums){
set.add(num & mask);// reserve Left bits and ignore Right bits
}
// now find out if there are two prefix with different i-th bit
// if there is, the new max should be current max with one 1 bit at i-th position, which is candidate
// and the two prefix, say A and B, satisfies:
// A ^ B = candidate
// so we also have A ^ candidate = B or B ^ candidate = A
// thus we can use this method to find out if such A and B exists in the set
int tmp = max | (1 << i); //in each iteration, there are pair(s) whoes Left bits can XOR to max
for(int prefix : set){
if(set.contains(tmp ^ prefix)) {
max = tmp;
break;
}
}
}
return max;
}
https://kingsfish.github.io/2017/12/15/Leetcode-421-Maximum-XOR-of-Two-Numbers-in-an-Array/
我们还需要用上一个异或的特性，假设
a和b产生了最终的答案max，即a ^ b = x，那么根据异或的特性，a ^ x = b。同理，a和b的最高位（前n位）也有相同的性质。
先以最高位为例子，我们可以把所有的数字的最高位放到一个
HashSet里面，然后使用1与set里面的所有数字进行异或，如果得出的结果仍然在set里面，那么最终结果的最高位必然为1，否则为0。也即，先假定结果为1，然后与set中所有数字异或，假定a与1异或得到结果b（a ^ 1 = b），而b仍然在set里面，那么说明set中有两个数字异或能得到1（a ^ b = 1）。否则，set中没有两个数字能够异或得到1，那么最终结果的最高位为1的假设失败，说明最终结果的最高位为0。以此类推可以得到第二位、第三位。。。的数字。
再做一下推广，我们将所有数字的前N位放到一个
HashSet里面，然后使用之前N-1位得到的最大值前缀prefix与set里面的所有数字进行异或，如果得出的结果仍然在set中，那么第N位必然为1，否则为0。
举个例子，给定数组
[14, 11, 7, 2]，二进制表示分别为[1110, 1011, 0111, 0010]。题目说了，数字最长不会超过32位，所以应从i = 31开始，但是所有数字中最多位4位数，简单起见，我直接从最高位i=3开始
|
|
最终答案是
1100 => 12，1011 ^ 0111 = 1100(11 ^ 7 = 12)。O(32n)=O(n)，空间复杂度上，我们使用了一个HashSet用于存储所有数字，因此空间复杂度是O(n)。和暴力搜索解法相比，典型的空间换时间
|
When I tried to solve this problem, I quickly came up with the idea that we should build the answer bit by bit from the most significant bit. For any bit, it's easy to see if it can be built from all the numbers(just test whether there exist a 0 and 1 for that bit), but I had the difficulty to make sure that we're only using two numbers to do the build. The '''set.contains(tmp^prefix)''' solve my problem, we don't need to remember which two numbers we used to get the previous bit, we just need to test whether a new candidate(tmp), can be built, and make sure that its built by using two numbers
http://www.cnblogs.com/grandyang/p/5991530.html
按位遍历，题目中给定了数字的返回不会超过231,那么最多只能有32位，我们用一个从左往右的mask，用来提取数字的前缀，然后将其都存入set中，我们用一个变量t，用来验证当前位为1再或上之前结果res，看结果和set中的前缀异或之后在不在set中，这里用到了一个性质，若a^b=c，那么a=b^c，因为t是我们要验证的当前最大值，所以我们遍历set中的数时，和t异或后的结果仍在set中，说明两个前缀可以异或出t的值，所以我们更新res为t，继续遍历，如果上述讲解不容易理解，那么建议自己带个例子一步一步试试，并把每次循环中set中所有的数字都打印出来，基本应该就能理解了
http://blog.csdn.net/mebiuw/article/details/52901057
不过两个解法的核心都是：
a^b = c ->a^c=b,b^c=a
// a^b = c ->a^c=b,b^c=a public int findMaximumXOR(int[] nums) { int max = 0, mask = 0; for(int i = 31; i >= 0; i--){ //mask从0x01 ->0x03等一直变化，取后i位 mask = mask | (1 << i); Set<Integer> set = new HashSet<>(); for(int num : nums){ set.add(num & mask); } //tmp表示当前的最大 int tmp = max | (1 << i); System.out.println(mask+" "+tmp+" "+max); for(int prefix : set){ //证明存在一个数使得tmp^x = prefix if(set.contains(tmp ^ prefix)) { max = tmp; break; } } } return max; }
https://segmentfault.com/a/1190000007283296
利用XOR的性质，a^b = c, 则有 a^c = b，且 b^c = a;
所以每次从高位开始，到某一位为止，所能获得的最大的数。设置变量mask用来表示能形成的值，每一次将mask和其他的num相与得到的值加入set，表示在当前这一位上，数组里有这么多prefix。
所以每次从高位开始，到某一位为止，所能获得的最大的数。设置变量mask用来表示能形成的值，每一次将mask和其他的num相与得到的值加入set，表示在当前这一位上，数组里有这么多prefix。
假定在某一位上的任意两数xor能得到的最大值是tmp,那么他一定满足a(xor)b = tmp,其中set.contains(a) && set.contains(b). 所以，我们只需要判断b(xor)tmp的结果是不是在当前这一位下的set内，就可以知道这个tmp能不能又这个set中的任意两个数组成。
public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
// test each bit pose, 判断能不能构成所需要的值；
for(int i = 31; i >= 0; i --) {
// 每次都在之前的基础上更新mask
mask = mask | (1 << i);
Set<Integer> set = new HashSet<>();
for(int num : nums) {
// add the number which has the mask as its prefix;
set.add(num & mask);
}
// 假设当前所能达到的最大值是这个temp值；
int tmp = max | (1 << i);
for(Integer prefix : set) {
if(set.contains(prefix ^ tmp)) {
// 如果能组成就直接break
max = tmp;
break;
}
}
}
return max;
}
利用异或的特性, 这题可以有更好的解法. 对于异或运算, 我们有
如果
a ^ b = c, 那么a ^ c = b.
根据这个定理, 我们从最高位开始找, 我们先将所有数的最高位存到一个
Set中. 然后, 我们假设最终答案的最高位为1, 将数列中所有数的最高位和1进行异或运算, 异或得到的结果仍然在Set中, 那么说明最终答案的最高位一定为1, (由定理可得1 ^ x = b <==> b ^ x = 1, 对与数x, 一定存在一个数b, 使得x ^ b = 1), 否则最高位的答案一定为0.
假设我们已经知道最终答案的最高
k位为prefix, 我们先将数列中所有数的最高k+1位存入Set中. 然后, 我们假设下一位的值为1, 将数列中所有数的最高k+1位与prefix*2 + 1进行异或运算, 如果异或得到的结果仍然在Set中, 那么说明最终答案的第k+1位一定为1, 否则, 最高位的答案一定为0.
因为
x ^ (prefix*2+1) = b <==> x ^ b = prefix*2+1, 即对于数x, 一定存在一个数b, 使得他们异或的结果为prefix*2+1.
因此, 我们可以对最终答案的32位进行依次判断, 最终得到异或的最大值.
该算法的时间复杂度为
O(32n) = O(n).X.
解法II Set数据结构 + 位运算
https://discuss.leetcode.com/topic/63299/python-6-lines-bit-by-bit/2
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
for (int i = 31; i >= 0; i--) {
mask |= (1 << i);
HashSet<Integer> set = new HashSet<Integer>();
for (int num : nums) {
set.add(num & mask); // reserve Left bits and ignore Right bits
}
/* Use 0 to keep the bit, 1 to find XOR
* 0 ^ 0 = 0
* 0 ^ 1 = 1
* 1 ^ 0 = 1
* 1 ^ 1 = 0
*/
int tmp = max | (1 << i); // in each iteration, there are pair(s) whoes Left bits can XOR to max
for (int prefix : set) {
if (set.contains(tmp ^ prefix)) {
max = tmp;
}
}
}
return max;
}I saw deeply and found out a very important xor feature I missed, that is: if a^b=c, then a^c=b, b^c=a. That's why the answer using this code:for(int prefix : set){ if(set.contains(tmp ^ prefix)) { max = tmp; break; } }
Agreed. Actually, this is the most important operation that made this code linear. Instead of choosing 2 from n, we verify if we can achieve maximum value -- 1 -- on each bit reversely based on the feature you have mentioned
public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
for(int i = 31; i >= 0; i--){
mask = mask | (1 << i);
Set<Integer> set = new HashSet<>();
for(int num : nums){
set.add(num & mask);
}
int tmp = max | (1 << i);
for(int prefix : set){
if(set.contains(tmp ^ prefix)) {
max = tmp;
break;
}
}
}
return max;
}
X. 解法III 字典树（Trie） + 位运算
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/130427/()-92
对于
[3,10,5,25,2,8]测试用例，如果使用O(n^2)算法，选取3与剩下的数进行异或。这个过程中对于5,10,8的二进制前28位异或结果是一样的，对于10,8而言前30位异或结果是一致的。很容易想到对数组中的数的二进制，构建前缀树。相同前缀的计算结果可复用，就能提升效率。建树
因为二进制元素只有0,1。考虑使用二叉树来构建前缀树。
- 根节点为符号位0
- 从高位到低位依次构建
- 左子树为1节点，又子树为0节点
[3,10,5,25,2,8]按照以上规则构建如下图（省略高位0）
那么这颗树包含了数组中所有的数字，从根节点到叶子节点的一条路径表示数组中的一个十进制数的二进制编码。
找最大异或值
对于
当前使得异或结果最大的数
当前指针
从第5位开始：
找到的x为5（00101）
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91059/Java-O(n)-solution-using-Trie25 (0000 0000 0000 0000 0000 0000 0001 1001) 而言，从第31-6位（都是正数，不考虑符号位），都为0,，且数组中的数字31-6位都为0，因此最大异或结果31-6位只能为0。当前使得异或结果最大的数
x为0000 0000 0000 0000 0000 0000 000? ????当前指针
curNode指向第图中根节点。从第5位开始：
5 1 x的第5位为0，则结果最大。应选择右分支，curNode = curNode->right4 1 x的第4位为0，则结果最大。应选择右分支，curNode = curNode->right3 0 x的第3位为1，则结果最大。应选择左分支，curNode = curNode->left2 0 x的第2位为1，则结果最大。应选择左分支，但树中左分支为null，只能选择右分支curNode = curNode->right 于是x的第2位为0。1 1 x的第1位为0，则结果最大。应选择右分支，但树中右分支为null，只能选择左分支curNode = curNode->left 于是x的第1位为1。找到的x为5（00101）
class Trie {
Trie[] children;
public Trie() {
children = new Trie[2];
}
}
public int findMaximumXOR(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
// Init Trie.
Trie root = new Trie();
for(int num: nums) {
Trie curNode = root;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode.children[curBit] == null) {
curNode.children[curBit] = new Trie();
}
curNode = curNode.children[curBit];
}
}
int max = Integer.MIN_VALUE;
for(int num: nums) {
Trie curNode = root;
int curSum = 0;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode.children[curBit ^ 1] != null) {
curSum += (1 << i);
curNode = curNode.children[curBit ^ 1];
}else {
curNode = curNode.children[curBit];
}
}
max = Math.max(curSum, max);
}
return max;
}It gets me TLE as well. Ditching theTrieclass and just usingObject[]gets it accepted in about 185 ms:
public int findMaximumXOR(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
// Init Trie.
Object[] root = {null, null};
for(int num: nums) {
Object[] curNode = root;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode[curBit] == null) {
curNode[curBit] = new Object[]{null, null};
}
curNode = (Object[]) curNode[curBit];
}
}
int max = Integer.MIN_VALUE;
for(int num: nums) {
Object[] curNode = root;
int curSum = 0;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode[curBit ^ 1] != null) {
curSum += (1 << i);
curNode = (Object[]) curNode[curBit ^ 1];
}else {
curNode = (Object[]) curNode[curBit];
}
}
max = Math.max(curSum, max);
}
return max;
}
We add the number into the trie and find the max possible XOR result at the same time.
Node.set() method will set the new node in the trie if needed and return the new node.
After setting the node, find the opposite bit in the trie to maximize the possible XOR result.
Node.set() method will set the new node in the trie if needed and return the new node.
After setting the node, find the opposite bit in the trie to maximize the possible XOR result.
public class Node {
Node one;
Node zero;
Node() {
this.one = null;
this.zero = null;
}
Node set(int n) {
if (n == 0) {
if (this.one == null) this.one = new Node();
return this.one;
}
if (this.zero == null) this.zero = new Node();
return this.zero;
}
}
public int findMaximumXOR(int[] nums) {
Node root = new Node();
int re = 0;
for (int num : nums) {
int digit = num;
int tmp = 0;
Node setNode = root;
Node findNode = root;
int pos = 30;
while (pos >= 0) {
digit = (num >> pos) & 1;
setNode = setNode.set(digit);
if (digit == 1) {
if (findNode.one != null) {
tmp = tmp | (1 << pos);
findNode = findNode.one;
} else {
findNode = findNode.zero;
}
} else {
if (findNode.zero != null) {
tmp = tmp | (1 << pos);
findNode = findNode.zero;
} else {
findNode = findNode.one;
}
}
pos--;
}
re = Math.max(re, tmp);
}
return re;
}Insert + Query at same time
X.
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/184434/JavaTrie99
根据题目描述，我们需要找到最大的异或值，异或代表了两个数的二进制的不同程度，且越高位越不一样，异或值就越大，由于是按位比较，所以使用Trie树来当做基础数据结构。
我们可以总结出以下几点：
- 因为整型的位数是固定的，排除第一位符号位，Trie树的高度是常数的，即最高
32层（包括root） - 由于只有
0和1两个子节点，所以为了节省空间，可以使用二叉树的方式（或者数组和HashMap均可） - 由于是异或，前缀位如果相同，异或值都是0，所以可以先找到第一个两个子节点都不为空的节点当做
root
class TrieNode {
int val;
TrieNode zero, one;
boolean isEnd;
}
class TrieTree {
TrieNode root;
public TrieTree() {
root = new TrieNode();
}
public void insert(int num) {
TrieNode cur = root;
int j = 1 << 30;
for (int i = 0; i < 31; i++) {
// 根据num在j位置的数目判断应该向0还是向1
int b = (j & num) == 0 ? 0 : 1;
if (b == 0 && cur.zero == null) {
cur.zero = new TrieNode();
}
if (b == 1 && cur.one == null) {
cur.one = new TrieNode();
}
cur = b == 0 ? cur.zero : cur.one;
j >>= 1;
}
cur.isEnd = true;
cur.val = num;
}
}
public int findMaximumXOR(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
TrieTree tree = new TrieTree();
for (int n : nums) {
tree.insert(n);
}
// 获取真正需要开始判断的root
TrieNode cur = tree.root;
while (cur.one == null || cur.zero == null) {
cur = cur.zero != null ? cur.zero : cur.one;
}
return maxHelper(cur.one, cur.zero);
}
/**
* 分治法，原则就是尽量使两个分支的高位不同
* one是1分支，zero是0分支，可以看做图中的左区和右区
* 1. 当1分支的下一位只有1时，找0分支的0，若没有，就找0分支的1
* 2. 当1分支的下一位只有0时，找0分支的1，若没有，就找0分支的0
* 3. 当1分支的下一位0，1均有时，看0分支：如果0分支只有1，则1分支走0，反之则走1
* 4. 当0，1两个分支均有两个下一位时，尝试【1分支走1，0分支走0】和【1分支走0，0分支走1】两条路线并取最大值
* */
private int maxHelper(TrieNode one, TrieNode zero) {
if (one.isEnd && zero.isEnd) {
return one.val ^ zero.val;
}
if (one.zero == null) {
return maxHelper(one.one, zero.zero == null ? zero.one : zero.zero);
} else if (one.one == null) {
return maxHelper(one.zero, zero.one == null ? zero.zero : zero.one);
} else if (zero.zero == null) {
return maxHelper(one.zero, zero.one);
} else if (zero.one == null) {
return maxHelper(one.one, zero.zero);
} else {
return Math.max(maxHelper(one.one, zero.zero), maxHelper(one.zero, zero.one));
}
}http://hankerzheng.com/blog/LeetCode-Maximum-XOR-of-Two-Numbers-in-an-Array
对输入的数组, 我们将其中的元素根据最高位的值分为两类, 最高位为
0的一类, 最高位为1的一类, 如果两类都不为空, 那么该问题的最终结果一定是从第一类中找一个数和第二类中的一个数进行异或得到的结果.
那么此题就可以优化为, 从两个数列中各取一个数, 求两个数按位异或结果的最大值. 因此, 我们可以设计一个
helper函数帮我们处理.
那么, 我们可以根据次高位再将数继续分成两类, 因此, 我们可以得到四个类,
arr00, arr01, arr10, arr11. 那么最终的解一定在(arr00, arr11), (arr10, arr01)中; 如果存在空集, 那么最终的解一定在(arr00, arr01), (arr11, arr10)中.
平均时间复杂度分析, 假设
O(n)表示helper函数的时间复杂度, 其中n表示传入helper两个数列的总长度. 那么我们有 O(n) = n + 2 * O(n/2), 化简后可得 O(n) = O(n log n) + O(n) = O(n log n) def findMaximumXOR(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def partition(nums, index):
mask = 1 << index
arr0, arr1 = [], []
for num in nums:
if num & mask:
arr1.append(num)
else:
arr0.append(num)
return arr0, arr1
def helper(arr0, arr1, index):
if not arr0 and not arr1:
return 0
if not arr0 or not arr1:
if index == 0:
return 0
arr = arr0 if arr0 else arr1
arr0, arr1 = partition(arr, index - 1)
return helper(arr0, arr1, index - 1)
if index == 0:
return arr0[0] ^ arr1[0]
arr00, arr01 = partition(arr0, index - 1)
arr10, arr11 = partition(arr1, index - 1)
if arr00 and arr11 or arr10 and arr01:
return max(helper(arr00, arr11, index - 1), helper(arr01, arr10, index - 1))
else:
return max(helper(arr01, arr11, index - 1), helper(arr00, arr10, index - 1))
return helper(nums, [], 32) public int findMaximumXOR(int[] nums) {
int max = Integer.MIN_VALUE;
int highBit = 0, count = 0;
for(int num: nums) max = Math.max(max, num);
while(count<=31){
if((max & (1<<count)) != 0) highBit = count;
count++;
}
List<Integer> isOne = new ArrayList<>();
List<Integer> notOne = new ArrayList<>();
for(int num: nums){
if(((num>>highBit) & 1) == 1) isOne.add(num);
else notOne.add(num);
}
return recur(isOne, notOne, highBit-1);
}
private int recur(List<Integer> isOne, List<Integer> notOne, int highBit){
if(isOne.size()==1 && notOne.size()==1) return isOne.get(0) ^ notOne.get(0);
List<Integer> l11 = new ArrayList<>();
List<Integer> l10 = new ArrayList<>();
List<Integer> l01 = new ArrayList<>();
List<Integer> l00 = new ArrayList<>();
for(int num: isOne){
if(((num>>highBit) & 1) != 0) l11.add(num);
else l10.add(num);
}
for(int num: notOne){
if(((num>>highBit) & 1) != 0) l01.add(num);
else l00.add(num);
}
int max = 0;
if(l11.size()!=0 && l00.size()!=0) max = recur(l11, l00, highBit-1);
if(l10.size()!=0 && l01.size()!=0) max = Math.max(max, recur(l10,l01,highBit-1));
return max;
}
Time: O(nlog(HighestBit))
http://bookshadow.com/weblog/2016/10/15/leetcode-maximum-xor-of-two-numbers-in-an-array/
求数组中两两数字的异或运算的最大值，朴素的解法是O(n ^ 2)，不满足题目要求。
异或运算（XOR）的实质是“同零异一”。
题目描述中a[i]的范围[0, 2^32)，至多有32位，因此可以通过位运算处理。
def findMaximumXOR(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def solve(nums0, nums1, mask):
if mask <= 1: return mask
mask /= 2
nums01 = [n for n in nums0 if n & mask]
nums00 = [n for n in nums0 if not n & mask]
nums11 = [n for n in nums1 if n & mask]
nums10 = [n for n in nums1 if not n & mask]
ans = 0
if nums10 and nums01:
ans = max(ans, solve(nums10, nums01, mask))
if nums00 and nums11:
ans = max(ans, solve(nums00, nums11, mask))
if not ans:
ans = solve(nums0, nums1, mask) - mask
return ans + mask * 2
mask = 1 << 31
while mask:
nums0 = [n for n in nums if not n & mask]
nums1 = [n for n in nums if n & mask]
if nums0 and nums1: break
mask >>= 1
return solve(nums0, nums1, mask)
|
TODO
https://discuss.leetcode.com/topic/64431/a-solution-based-on-bartoszkp-s-with-missing-test-cases
https://discuss.leetcode.com/topic/63759/c-o-nlogk-solution-with-ordering-bits-with-o-logk-additional-memory-for-recursion-stack
http://www.1point3acres.com/bbs/thread-202685-3-1.html
Related:
https://www.geeksforgeeks.org/minimum-xor-value-pair/
Given an array of integers. Find the pair in an array which has minimum XOR value.
Examples :
Examples :
Input : arr[] = {9, 5, 3}
Output : 6
All pair with xor value (9 ^ 5) => 12,
(5 ^ 3) => 6, (9 ^ 3) => 10.
Minimum XOR value is 6
A further more Efficient solution can solve the above problem in O(n) time under the assumption that integers take fixed number of bits to store. The idea is to use Trie Data Structure. Below is algorithm.
1). Create an empty trie. Every node of trie contains two children
for 0 and 1 bits.
2). Initialize min_xor = INT_MAX, insert arr[0] into trie
3). Traversal all array element one-by-one starting from second.
a. First find minimum setbet difference value in trie
do xor of current element with minimum setbit diff that value
b. update min_xor value if required
c. insert current array element in trie
4). return min_xor
