Java 中的最小 XOR 值对

2024 年 9 月 10 日 | 阅读 8 分钟

给定一个包含非负数的数组，我们的任务是找出代表数组中两个数字的最小 XOR 值的值。考虑以下示例。

示例 1

输入： int a[] = {10, 8, 5, 3, 1};

输出 2

解释： 在给定的数组中，我们可以形成 10 对

(10, 8) = 10 ^ 8 = 2		(10, 5) = 10 ^ 5 = 15
(10, 3) = 10 ^ 3 = 9		(10, 1) = 10 ^ 1 = 11
(8, 5) = 8 ^ 5 = 13		(8, 3) = 8 ^ 3 = 11
(8, 1) = 8 ^ 1 = 9		(5, 3) = 5 ^ 3 = 6
(5, 1) = 5 ^ 1 = 4		(3, 1) = 3 ^ 1 = 2

我们看到所有上述对的最小 XOR 值为 2。
请注意，无需再形成一对 (8, 10)。这是因为 XOR 操作是可交换的，并且对 (10, 8) 已经考虑过。

示例 2

输入： int a[] = {3, 5, 7, 2};

输出 1

解释： 在给定的数组中，我们可以形成 6 对。

(3, 5) = 3 ^ 5 = 6		(3, 7) = 3 ^ 7 = 4
(3, 2) = 3 ^ 2 = 1		(5, 7) = 5 ^ 7 = 2
(5, 2) = 5 ^ 2 = 7		(7, 2) = 7 ^ 2 = 5

我们看到所有上述对的最小 XOR 值为 1。

朴素方法

方法很简单，找出给定数组中存在的每个元素的对。计算每对的 XOR 并找出最小 XOR 值。让我们在以下程序中看看它是如何实现的。

文件名： MinXORVal.java

public class MinXORVal
{

// a method that finds the minimum between a & b
public int min(int a, int b)
{
    return (a > b) ? b : a;
}

// a method that finds the minimum XOR value
public int findMinXorVal(int arr[], int size)
{
    int ans = Integer.MAX_VALUE;
    for(int i = 0; i < size; i++)
    {
        for(int j = i + 1; j < size; j++)
        {
            ans = min(ans, (arr[i] ^ arr[j]));
        }
    }
    
    return ans;
}


// main method
public static void main(String argvs[])
{
// creating an object of the class MinXORVal
MinXORVal obj = new MinXORVal();

// input array
int a[] = {10, 8, 5, 3, 1};

int size = a.length;

int minVal = obj.findMinXorVal(a, size);

System.out.println("For the array: "); 

for(int idx = 0; idx < size; idx++)
{
System.out.print(a[idx] + " "); 
}
System.out.println();
System.out.println("The minimum XOR value is: " + minVal);
System.out.println();

// input array
int a1[] = {3, 5, 7, 2};

size = a1.length;

minVal = obj.findMinXorVal(a1, size);

System.out.println("For the array: "); 

for(int idx = 0; idx < size; idx++)
{
System.out.print(a1[idx] + " "); 
}
System.out.println();
System.out.println("The minimum XOR value is: " + minVal);
}
}

输出

For the array: 
10 8 5 3 1 
The minimum XOR value is: 2

For the array: 
3 5 7 2 
The minimum XOR value is: 1

时间复杂度：在上面的程序中，我们在 findMinXorVal() 方法中使用了两层嵌套的 for 循环。由于外层循环的每次迭代，内层循环的时间复杂度为 O(n)。因此，该程序 O(n2) 的总体时间复杂度，其中 n 是输入数组中元素的总数。

使用排序

在此方法中，我们将对输入数组进行排序，并使用单个循环找到最小 XOR 值。排序方法有效，因为两个相近的数字的 XOR 值比相距较远的数字的 XOR 值要小。例如：1 ^ 8 = 9 & 4 ^ 5 = 1。这是因为 4 和 5 之间的差值为 1，而 1 和 8 之间的差值为 7。因此，当我们进行排序时，彼此接近的数字会排在一起，然后我们只需要运行一个循环并找到连续元素的 XOR。观察下面的程序。

文件名： MinXORVal1.java

// import statement
import java.util.Arrays;

public class MinXORVal1
{

// a method that finds the minimum between a & b
public int min(int a, int b)
{
    return (a > b) ? b : a;
}

// a method that finds the minimum XOR value
public int findMinXorVal(int arr[], int size)
{
    int ans = Integer.MAX_VALUE;    
    Arrays.parallelSort(arr); // sorting the array
    for(int i = 0; i < size - 1; i++)
    {
        // computing XOR of consecutive elements after
        // sorting the array and finding the minimum of those XOR values
        ans = min(ans, (arr[i] ^ arr[i + 1]));    
    }    
    return ans;
}
// main method
public static void main(String argvs[])
{
// creating an object of the class MinXORVal1
MinXORVal1 obj = new MinXORVal1();
// input array
int a[] = {10, 8, 5, 3, 1};
int size = a.length;
System.out.println("For the array: "); 
for(int idx = 0; idx < size; idx++)
{
System.out.print(a[idx] + " "); 
}
System.out.println();
int minVal = obj.findMinXorVal(a, size);
System.out.println("The minimum XOR value is: " + minVal);
System.out.println();
// input array
int a1[] = {3, 5, 7, 2};
size = a1.length;
System.out.println("For the array: "); 
for(int idx = 0; idx < size; idx++)
{
System.out.print(a1[idx] + " "); 
}
System.out.println();
minVal = obj.findMinXorVal(a1, size);
System.out.println("The minimum XOR value is: " + minVal);
}
}

输出

For the array: 
10 8 5 3 1 
The minimum XOR value is: 2
For the array: 
3 5 7 2 
The minimum XOR value is: 1

时间复杂度：在上面的程序中，我们使用了排序和一个 for 循环。排序需要 O(nlog(n)) 时间，循环需要 O(n) 时间。因此，O(n + nlog(n)) 的上述程序的总体时间复杂度，其中 n 是输入数组中元素的总数。请注意，此方法比前一种方法更好。

使用 TRIE

使用 TRIE，我们将获得最优化的解决方案，因为我们可以在甚至少于 O(nlog(n)) 的时间内解决问题。让我们看看它的算法。

步骤 1：制作一个空的 TRIE，使得 TRIE 的每个节点都有两个子节点，一个用于 0 位，另一个用于 1 位。

步骤 2：初始化 minXorVal 为 INT_MAX，并将 a[0] 插入 TRIE。

步骤 3：逐个遍历数组中的所有元素，从第二个元素开始，并执行以下操作

首先，在 TRIE 中查找最小的位值差。然后将当前元素与与该值不同的最小位进行 XOR。
如果需要，则更新 minXorVal 值
插入数组的当前元素

步骤 4：返回 minXorVal

文件名： MinXORVal2.java

public class MinXORVal2 
{
// a method that finds the minimum between a & b
public static int min(int a, int b)
{
return (a > b) ? b : a;
}

// maximum no of bits present in a number
public static final int MAX_SIZE = 32;

// a class for Trie Trie
static class Trie 
{
int val; // is used in the leaf node


Trie[] children = new Trie[2];

public Trie()
{
val = 0;
children[0] = null;
children[1] = null;
}
}
static Trie rt;

// a method that inserts the number num in the TRIE
public static void insert(int num)
{
Trie tmp = rt;

// starting from the most significant bit, we insert all the bit
// of the num one-by-one in the TRIE
for (int j = MAX_SIZE - 1; j >= 0; j--) 
{
// Finding the current bit in the given prefix
int currentBit = (num & (1 << j)) >= 1 ? 1 : 0;

// Adding a new node in the TRIE
if (tmp != null && tmp.children[currentBit] == null)
{
tmp.children[currentBit] = new Trie();
}

tmp = tmp.children[currentBit];
}

// storing the value at the leaf node
tmp.val = num;
}

// Returns minimum XOR value of an integer inserted
// in Trie and given key.
static int minXORUtil(int num)
{
Trie tmp = rt;

for (int j = MAX_SIZE - 1; j >= 0; j--) 
{
// Finding the current bit in the given prefix
int currentBit = (num & (1 << j)) >= 1 ? 1 : 0;

// Traversing Trie, to look after the prefix that has
// the same bit
if (tmp.children[currentBit] != null)
{
tmp = tmp.children[currentBit];
}

// if no same bit is found then look for 
// the opposite bit
else if (tmp.children[1 - currentBit] != null)
{
tmp = tmp.children[1 - currentBit];
}
}

// return XOR value of minimum bit difference value
// so that we get minimum xor value
return num ^ tmp.val;
}

// a method that returns the minimum XOR value of a pair in the array a[0 ... size - 1]
public int findMinXOR(int a[], int size)
{
int minXorVal = Integer.MAX_VALUE; // Initialize the result

// creating a Trie node and inserting the first element in it
rt = new Trie();
insert(a[0]);

// Traversing all the elements of the array and finding the minimum XOR
// for each & every element
for (int j = 1; j < size; j++) 
{
// Finding the minimum XOR value of the current element 
// with the previous elements that has been inserted in TRIE
minXorVal = Math.min(minXorVal, minXORUtil(a[j]));

// insert current array value into Trie
insert(a[j]);
}
return minXorVal;
}

// Main Method
public static void main(String argvs[])
{
// creating an object of the class MinXORVal2
MinXORVal2 obj = new MinXORVal2();

// input array
int a[] = {10, 8, 5, 3, 1};

int size = a.length;

System.out.println("For the array: "); 

for(int idx = 0; idx < size; idx++)
{
System.out.print(a[idx] + " "); 
}
System.out.println();
int minVal = obj.findMinXOR(a, size);

System.out.println("The minimum XOR value is: " + minVal);

System.out.println();

// input array
int a1[] = {3, 5, 7, 2};

size = a1.length;

System.out.println("For the array: "); 

for(int idx = 0; idx < size; idx++)
{
System.out.print(a1[idx] + " "); 
}
System.out.println();
minVal = obj.findMinXOR(a1, size);
System.out.println("The minimum XOR value is: " + minVal);

}
}

输出

For the array: 
10 8 5 3 1 
The minimum XOR value is: 2

For the array: 
3 5 7 2 
The minimum XOR value is: 1

时间复杂度：O(n)，其中 n 是数组中元素的总数。

下一个主题Java 中的 Iccanobif 数字

Java 中的最小 XOR 值对

朴素方法

使用排序

使用 TRIE

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的最小 XOR 值对

朴素方法

使用排序

使用 TRIE

相关帖子

Java Cron 表达式

Java 中的 EnumMap

Java 中的 Kaprekar 数

Advantages of JavaBeans

Java 本地化

Twin Prime Numbers

Collections Sort in Java 8

Java ASCII 表

BreakIterator previous() method in Java with Examples

RuleBasedCollator compare() method in Java with Example

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器