极客教程Java中的最大XOR值
我们得到了两个包含非负数的数组作为输入。我们的任务是找到p ^ q的最大值，其中p是第一个数组的任何元素，q是第二个数组的任何元素。在显示最大值的同时，也要显示那些通过XOR得到最大值的一对。如果有多个配对给出了最大的XOR值，那么就打印在第一个输入数组中p值排在前面的那个配对。
例1 :
输入
int inArr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
int inArr2[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11}。
输出
30，对。10, 30
解释 。
在所有可能的配对中，给定的输入数组的最大XOR值是30，它来自于元素10（来自第一个数组）和20（来自第二个数组）。
例2 :
输入
int inArr1[] = {25, 10, 2, 8, 5, 3}
int inArr2[] = {25, 10, 2, 8, 5, 3}。
输出
28，对：25，5
解释 。
给定的输入数组的最大XOR值是28，它来自于元素25（来自第一个数组）和5（来自第二个数组）。请注意，如果我们从第一个数组中抽取元素5，从第二个数组中抽取元素25，我们将得到相同的结果。然而，元素5是来自第一个数组，而且在元素25之后。因此，它被避免了。
简单的方法：使用嵌套For-loop
使用嵌套的for-loop，我们可以找到最大值。外循环在第一个数组中进行迭代。对于外循环的每一次迭代，在内循环的帮助下遍历第二个数组的每个元素。对于内循环的每次迭代，找出外循环和内循环的循环变量分别指向的元素的XOR值。同时，将当前的XOR值与到目前为止发现的最大XOR值进行比较。如果当前的XOR值大于到目前为止发现的最大XOR值，则更新最大XOR值。参与最大XOR值的元素是一对。
文件名： MaxXorVal.java
public class MaxXorVal
{
// for storing the pair
// that gives the maximum XOR value
static int a1;
static int a2;
// a method that finds the maximum XOR value and the pair
// that is responsible for that maximum XOR value
public int findMaximumXorVal(int inArr1[], int inArr2[])
{
// size of the input arrays
int s1 = inArr1.length;
int s2 = inArr2.length;
int maxVal = -1;
// outer loop for traversing through the array inArr1
for(int p = 0; p < s1; p++)
{
// inner loop for traversing through the array inArr2
for(int q = 0; q < s2; q++)
{
int tmpVal = inArr1[p] ^ inArr2[q];
if(tmpVal > maxVal)
{
// storing the maximum value and
// the elements that are responsible
// for the maximum value
maxVal = tmpVal;
a1 = inArr1[p];
a2 = inArr2[q];
}
}
}
return maxVal;
}
// main method
public static void main(String args[])
{
// creating an object of the class MaxXorVal
MaxXorVal obj = new MaxXorVal();
// input arrays
int inArr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int inArr2[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11};
int ans = obj.findMaximumXorVal(inArr1, inArr2);
System.out.println("The maximum XOR value is: " + ans);
System.out.println("The pair that gives the max XOR value is: (" + a1 + ", " + a2 + ")");
System.out.println("\n");
// input arrays
int inArr3[] = {25, 10, 2, 8, 5, 3};
int inArr4[] = {25, 10, 2, 8, 5, 3};
ans = obj.findMaximumXorVal(inArr3, inArr4);
System.out.println("The maximum XOR value is: " + ans);
System.out.println("The pair that gives the max XOR value is: (" + a1 + ", " + a2 + ")");
System.out.println("\n");
}
}
输出 。
The maximum XOR value is: 30
The pair that gives the max XOR value is: (10, 20)
The maximum XOR value is: 28
The pair that gives the max XOR value is: (25, 5)
复杂度分析： 该程序使用嵌套for-loops，其中外循环运行O(m)次，外循环的每一次迭代，内循环运行O(n)次。因此，该程序的时间复杂度为O(m x n)，其中m是第一个数组中存在的元素总数，n是第二个数组中存在的元素总数。程序的空间复杂度是O(1)，因为程序没有使用任何额外的空间。
现在，是时候做一些优化了。
方法：使用TRIE
我们可以通过寻找那些最左边的比特值不同的元素来实现最大的XOR值。换句话说，如果第一个数组中的元素 “P “的第j位的值是1，那么第二个数组中的元素 “Q “的第j位应该是0，反之亦然。为了找到这些元素，我们将从最重要的位（最左边的位）开始，然后向右走，直到我们找到一个在元素’P’和’Q’的二进制表示中数值不同的位。
为了有效地检查第一个数组中的值，我们可以对第二个数组中的每个元素使用一个TRIE数据结构。对于第二个数组中的每个元素，我们做二进制转换，并将每个比特插入TRIE中。注意，根将是最重要的位。
现在，我们将遍历第一个数组的每一个元素，并将其转换为二进制表示，并将从最重要的位开始遍历所有的位。如果当前的位是’0’，那么我们就移动到三角形中的’1’子，如果有的话，反之亦然。最后，我们将从第一个数组中找到一个相应的元素，使其与第二个数组的当前元素的XOR值为最大。最后，我们将返回所有找到的此类XOR值的最大值。
文件名： MaxXorVal1.java
public class MaxXorVal1
{
// for storing the pair
// that gives the maximum XOR value
static int a1;
static int a2;
// it is because we are dealing with the 32 bits numbers
private static final int INT_SIZE = 32;
// a class for implementing the TRIE data structure
class TrieNode
{
public int val;
// values for keeping in the leaf node
public TrieNode children[];
public TrieNode()
{
children = new TrieNode[2];
val = 0;
children[0] = null;
children[1] = null;
}
}
// Utility method for creating a new node
private TrieNode getNode()
{
TrieNode newNde = new TrieNode();
newNde.val = 0;
newNde.children[0] = newNde.children[1] = null;
return newNde;
}
// Utility method for inserting a new key in TRIE.
private void insertKey(TrieNode rt, int ky)
{
TrieNode tmp = rt;
// Starting from the most significant bit,
// insert all of the bits of ky into TRIE one by one.
for (int j = INT_SIZE - 1; j >= 0; j--)
{
// Find the current bit in the given prefix
int currBit = (ky & (1 << j)) >= 1 ? 1 : 0;
// Adding a new Node into TRIE
if (tmp.children[currBit] == null)
{
tmp.children[currBit] = getNode();
}
tmp = tmp.children[currBit];
}
// Storing value of the ky in the leafNode
tmp.val = ky ;
}
// Utility method for finding the maximum XOR value of an integer inserted in TRIE and
// given key.
private int[] findMaximum(TrieNode rt, int key)
{
TrieNode tmp = rt;
for (int j = INT_SIZE - 1; j >= 0; j--)
{
// Finding the current bit in
// the given prefix
int currBit = (key & (1 << j)) >= 1 ? 1 : 0;
// Traversing TRIE, looking for the prefix that has the opposite bit.
if (tmp.children[1 - currBit] != null)
{
tmp = tmp.children[1 - currBit];
}
// If there is no opposite bit, then look for the same bit.
else if (tmp.children[currBit] != null)
{
tmp = tmp.children[currBit];
}
}
int tempArr[] = new int[2];
tempArr[0] = tmp.val;
tempArr[1] = key ^ tmp.val;
// Returning XOR with the value at the leaf node.
return tempArr;
}
public int findMaximumXorVal(int list1[], int list2[], int s1, int s2)
{
// Initializing the result.
int maximumVal = Integer.MIN_VALUE;
// Create a TRIE and insert all of the elements of the first array into TRIE.
TrieNode rt = getNode();
for (int j = 0; j < s1; j++)
{
insertKey(rt, list1[j]);
}
// For every element in the second array, compute the maximum XOR value from TRIE.
for (int j = 0 ; j < s2; j++)
{
// Finding the maximum XOR value of the current element with
// the elements inserted in TRIE.
int tempArr[] = findMaximum(rt, list2[j]);
if(tempArr[1] > maximumVal)
{
// if the control reaches here
// then it means we have found a value that is more than the current
// maximum value. Hence, we have to update the pair as well as the
// maximum value.
a1 = list2[j]; // for pair
a2 = tempArr[0]; // for pair
maximumVal = tempArr[1]; // for maximum XOR value
}
}
return maximumVal;
}
// main method
public static void main(String args[])
{
// creating an object of the class MaxXorVal1
MaxXorVal1 obj = new MaxXorVal1();
// input arrays
int inArr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int inArr2[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11};
int ans = obj.findMaximumXorVal(inArr2, inArr1, inArr2.length, inArr1.length);
System.out.println("The maximum XOR value is: " + ans);
System.out.println("The pair that gives the max XOR value is: (" + a1 + ", " + a2 + ")");
System.out.println("\n");
// input arrays
int inArr3[] = {25, 10, 2, 8, 5, 3};
int inArr4[] = {25, 10, 2, 8, 5, 3};
ans = obj.findMaximumXorVal(inArr4, inArr3, inArr4.length, inArr3.length);
System.out.println("The maximum XOR value is: " + ans);
System.out.println("The pair that gives the max XOR value is: (" + a1 + ", " + a2 + ")");
System.out.println("\n");
}
}
输出 。
The maximum XOR value is: 30
The pair that gives the max XOR value is: (10, 20)
The maximum XOR value is: 28
The pair that gives the max XOR value is: (25, 5)
复杂性分析： 该程序使用了两个循环，一个用于第一个阵列，另一个用于第二个阵列。而且，这些循环不是嵌套的。对于给定数组中的每一个数字，我们也运行一个从32到0的循环。因此，程序的时间复杂度是O(32 x (m + n))。另外，该程序使用了一个TRIE数据结构，用来存储第二个数组的32位数字。因此，该程序的空间复杂度为O(32 x n)，其中m是第一个数组的大小，n是第二个数组的大小。