Java 中查找数字的奇数出现次数

给定一个非负整数数组，其中每个数字都出现偶数次，只有一个数字出现奇数次。任务是找到出现奇数次的那个数字。

示例

输入: a[] = {7, 4, 5, 4, 5, 7, 5, 9, 8, 9, 6, 8, 6}

输出 5

解释: 除了 5 之外，所有其他数字都出现了偶数次。注意数字 5 在输入数组中出现了 3 次，这是奇数。

输入: a[] = {4, 3, 9, 3, 4, 9, 4, 7, 4, 7, 4}

输出 4

解释: 除了 4 之外，所有其他数字都出现了偶数次。注意数字 4 在输入数组中出现了 5 次，这是奇数。

朴素方法

最直接的解决方案是使用两个循环。外层循环选择一个数字，内层循环计算该数字出现的频率。如果出现频率是偶数，则我们丢弃该数字。如果出现频率是奇数，则我们返回该数字。

文件名: OddOccurrence.java

输出

In the following input array: 
7 4 5 4 5 7 5 9 8 9 6 8 6 
The number whose occurrence is odd is: 5

In the following input array: 
4 3 9 3 4 9 4 7 4 7 4 
The number whose occurrence is odd is: 4

时间复杂度: 上述程序使用了两个嵌套的循环。因此，时间复杂度为 O(n²)，其中 n 是输入数组中的总元素数。

空间复杂度: 上述程序不使用任何额外空间。因此，上述程序的空间复杂度为 O(1)。

使用数组查找出现奇数次的数字

我们可以使用一个数组来存储元素的出现频率。然后，我们可以检查出现频率为奇数的数字。以下程序演示了这一点。

文件名: OddOccurrence1.java

输出

In the following input array: 
7 4 5 4 5 7 5 9 8 9 6 8 6 
The number whose occurrence is odd is: 5

In the following input array: 
4 3 9 3 4 9 4 7 4 7 4 
The number whose occurrence is odd is: 4

时间复杂度: 上述程序使用了三个循环。但是，这些循环不是嵌套的。因此，时间复杂度为 O(n)，其中 n 是输入数组中的总元素数。

空间复杂度: 上述程序使用了一些额外空间。我们看到程序中使用了数组来存储元素的出现频率。上述程序的空间复杂度为 O(maxElement)，其中 maxElement 是输入数组中的最大元素。

此方法的缺点是用于存储频率的数组中存在未使用的空间。例如：对于数组 {7, 4, 5, 4, 5, 7, 5, 9, 8, 9, 6, 8, 6}，内存将被分配给数组 storeFreq[] 中的 10 个元素。但是，只有 storeFreq[4]、storeFreq[5]、storeFreq[6]、storeFreq[7]、storeFreq[8] 和 storeFreq[9] 会被使用。因此，为 storeFreq[0]、storeFreq[1]、storeFreq[3] 以及更多元素分配的内存将白白浪费。如果输入是 {1000, 1, 1000}，情况会更糟。在这种情况下，我们必须为 1001 个元素分配内存，而其中只有 2 个元素（一个用于 1000，另一个用于 1）的内存将被使用。其余的内存分配都是无用的。为了避免这种内存浪费，我们应该使用哈希表。

使用哈希表查找出现奇数次的数字

我们也可以使用哈希表来存储元素的出现频率。之后，我们可以检查出现频率为奇数的数字。以下程序对此进行了说明。

文件名: OddOccurrence2.java

输出

In the following input array: 
7 4 5 4 5 7 5 9 8 9 6 8 6 
The number whose occurrence is odd is: 5

In the following input array: 
4 3 9 3 4 9 4 7 4 7 4 
The number whose occurrence is odd is: 4

时间复杂度: 上述程序使用了两个循环。但是，这些循环不是嵌套的。因此，时间复杂度为 O(n)，其中 n 是输入数组中的总元素数。

空间复杂度: 上述程序使用了一些额外空间。请注意程序中使用了哈希表来存储元素及其出现频率。显然，哈希表不能存储比输入数组中存在的元素更多的元素。因此，上述程序的空间复杂度为 O(n)，其中 n 是输入数组中的总元素数。

使用按位异或运算符查找出现奇数次的数字

在此方法中，我们将使用按位异或 (^) 运算来查找输入数组中数字的奇数次出现。此方法背后的思想是异或运算是可交换的，即：

我们所做的只是重新排列数字，使相同的数字分组在一起。而且，我们知道任何两个相同数字的异或运算结果为 0。因此：

7 ^ 7 = 0, 4 ^ 4 = 0, 5 ^ 5 ^ 5 = 0 ^ 5 = 5, 9 ^ 9 = 0, 8 ^ 8 = 0, 6 ^ 6 = 0

因此，我们得到：

7 ^ 7 ^ 4 ^ 4 ^ 5 ^ 5 ^ 5 ^ 9 ^ 9 ^ 8 ^ 8 ^ 6 ^ 6 = 0 ^ 0 ^ 5 ^ 0 ^ 0 ^ 0 = 5

以下程序显示了这一点。

文件名: OddOccurrence3.java

输出

In the following input array: 
7 4 5 4 5 7 5 9 8 9 6 8 6 
The number whose occurrence is odd is: 5

In the following input array: 
4 3 9 3 4 9 4 7 4 7 4 
The number whose occurrence is odd is: 4

时间复杂度: 上述程序仅使用一个循环。因此，时间复杂度为 O(n)，其中 n 是输入数组中的总元素数。

空间复杂度: 上述程序不使用任何额外空间。因此，上述程序的空间复杂度为 O(1)。