在本教程中，我们将看到如何查找数组中的奇数次数。

问题：

我们被赋予了一系列整数。
除了一个之外，所有数字甚至都会出现。
我们需要查找奇数时间发生的数字。
我们需要用O(n)时间复杂度和O(1)空间复杂度来解决它。
例如：

int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20};
Number which occurs odd number of times is : 50

解决方案：

解决方案1：使用两个循环并比较元素：

这是这个问题的蛮力解决方案，但它需要O(n * n)时间复杂度。

解决方案2：使用散列

我们可以使用键和数字并计数为值，并且只要重复键，即可将计数器递增1.

int getOddTimesElementHashing(int ar[]) 
{
	int i;
 
	HashMap<Integer,Integer> elements=new HashMap<Integer,Integer>();
	for (i = 0; i < ar.length; i++) 
	{
		int element=ar[i];
		if(elements.get(element)==null)
		{
			elements.put(element, 1);
 
		}
		else
			elements.put(element, elements.get(element)+1);
	}
	for (Entry<Integer,Integer> entry:elements.entrySet()) { 
		if(entry.getValue()%2==1)
		{
			return entry.getKey();
		}
 
	} 
	return -1;
}

但上面的解决方案需要空间复杂度的O(n)。

解决方案3：使用XOR操作：

我们可以为所有元素进行按位XOR操作，并将为我们提供奇数次数的元素。

int getOddTimesElement(int ar[]) 
  {
      int i;
      int result = 0;
      for (i = 0; i < ar.length; i++) 
      {
       result = result ^ ar[i];
      }
      return result;
  }

上面的算法解决了O(n)时间复杂度和O(1)空间复杂度的问题，这是上述程序的最佳解决方案。

Java程序以查找数组中发生的数量奇数：

package org.igi.theitroad;
 
//Java program to find the element occurring odd number of times
 
public class NumberOddTimesMain 
{
	int getOddTimesElement(int ar[]) 
	{
		int i;
		int result = 0;
		for (i = 0; i < ar.length; i++) 
		{
			//XOR operation
			result = result ^ ar[i];
		}
		return result;
	}
 
 
	public static void main(String[] args) 
	{
		NumberOddTimesMain occur = new NumberOddTimesMain();
		int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20};
		System.out.println("Number which occurs odd number of times is : "+occur.getOddTimesElement(array));
	}
}

运行上面的程序时，我们将得到以下输出：

Number which occurs odd number of times is : 50