Java 中除了自身之外的数组元素异或

这是一个在顶级 IT 公司（如 Google、Amazon、TCS、Accenture 等）面试中经常被问到的问题。通过解决这个问题，人们希望考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将讨论 Java 中数组元素除了自身之外的异或运算，采用不同的方法和逻辑。此外，我们还将为此创建 Java 程序。

问题陈述

我们给定一个只包含非负元素的数组。任务是创建另一个数组（例如 output[]），使得 output[i] 包含输入数组中除了 input[i] 之外所有元素的异或运算结果。以下示例对此进行了说明。

让我们通过示例来理解。

示例 1

输入: int input[] = {4, 7, 9, 3, 2, 5, 6}

输出: output[] = {12, 15, 1, 11, 10, 13, 14}

解释: 如果我们排除当前元素并对其余元素进行异或运算，我们得到上述输出。请观察以下内容。

output[0] = 7 ^ 9 ^ 3 ^ 2 ^ 5 ^ 6 = 12

output[1] = 4 ^ 9 ^ 3 ^ 2 ^ 5 ^ 6 = 15

output[2] = 4 ^ 7 ^ 3 ^ 2 ^ 5 ^ 6 = 1

output[3] = 4 ^ 7 ^ 9 ^ 2 ^ 5 ^ 6 = 11

output[4] = 7 ^ 9 ^ 3 ^ 5 ^ 6 = 10

output[5] = 4 ^ 7 ^ 9 ^ 3 ^ 2 ^ 6 = 13

output[6] = 4 ^ 7 ^ 9 ^ 3 ^ 2 ^ 5 = 14

示例 2

输入: int input[] = {0, 6, 2, 9}

输出: output[] = {13, 11, 15, 4}

说明

output[0] = 6 ^ 2 ^ 9 = 13

output[1] = 0 ^ 2 ^ 9 = 11

output[2] = 0 ^ 6 ^ 9 = 15

output[3] = 0 ^ 6 ^ 2 = 4

问题解决方案

朴素方法

在此方法中，我们将使用嵌套的 for 循环来计算除了自身之外所有元素的异或运算结果。

文件名: XorArrElements.java

输出

For the input array: 
4 7 9 3 2 5 6 
The output array is: 
12 15 1 11 10 13 14 

For the input array: 
0 6 2 9 
The output array is: 
13 11 15 4

复杂度分析: 该程序使用嵌套的 for 循环。因此，上述程序的时间复杂度为 O(n²)，其中 n 是输入数组中存在的元素总数。该程序没有使用任何额外的空间。因此，程序的空间复杂度是常数，即 O(1)。

程序的时??复杂度可以进一步降低。以下方法对此进行了说明。

计算所有元素的异或运算

我们知道，如果两个数字相等，它们的异或运算结果总是零。因此，我们可以计算所有元素的异或运算结果，并且要排除任何元素，只需将所有元素的异或运算结果与该元素进行异或运算。让我们通过一个例子来理解它。

int arr[] = {a1, a2, a3, a4, a5, a6}, size = 6

因此，output[0] = (a1 ^ a2 ^ a3 ^ a4 ^ a5 ^ a6) ^ a1，

我们知道异或运算是可交换的。因此，我们可以将 a1 分组在一起

output[0] = (a1 ^ a1 ^ a2 ^ a3 ^ a4 ^ a5 ^ a6) = 0 ^ a2 ^ a3 ^ a4 ^ a5 ^ a6 (因为 a1 ^ a1 = 0)

这正是除了元素本身之外所有元素的异或运算结果。以下程序使用了相同的概念。

文件名: XorArrElements1.java

输出

For the input array: 
4 7 9 3 2 5 6 
The output array is: 
12 15 1 11 10 13 14 

For the input array: 
0 6 2 9 
The output array is: 
13 11 15 4

复杂度分析: 该程序的时间复杂度为 O(n)，其中 n 是输入数组中存在的元素总数。程序的空间复杂度与上述相同。