本文概述
给定一个正整数数组。除一个数字为奇数次外, 所有数字均出现偶数次。在O(n)时间和恒定空间中找到数字。
例子 :
Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3
Input : arr = {5, 7, 2, 7, 5, 2, 5}
Output : 5
C#
//C# program to find the element
//occurring odd number of times
using System;
class GFG {
//Function to find the element
//occurring odd number of times
static int getOddOccurrence( int [] arr, int arr_size)
{
for ( int i = 0; i <arr_size; i++) {
int count = 0;
for ( int j = 0; j <arr_size; j++) {
if (arr[i] == arr[j])
count++;
}
if (count % 2 != 0)
return arr[i];
}
return -1;
}
//Driver code
public static void Main()
{
int [] arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 };
int n = arr.Length;
Console.Write(getOddOccurrence(arr, n));
}
}
//This code is contributed by Sam007
输出如下:
5
一种更好的解决方案是使用哈希。使用数组元素作为键, 并将其计数作为值。创建一个空的哈希表。一对一遍历给定的数组元素并存储计数。该解决方案的时间复杂度为O(n)。但是它需要额外的空间来进行哈希处理。
程序:
C#
//C# program to find the element
//occurring odd number of times
using System;
class GFG {
//Function to find the element
//occurring odd number of times
static int getOddOccurrence( int [] arr, int arr_size)
{
int res = 0;
for ( int i = 0; i <arr_size; i++) {
res = res ^ arr[i];
}
return res;
}
//Driver code
public static void Main()
{
int [] arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 };
int n = arr.Length;
Console.Write(getOddOccurrence(arr, n));
}
}
//This code is contributed by Sam007
输出如下:
5
请参考完整的文章查找出现次数的奇数更多细节!