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是第二个数组的大小。