C#程序查找出现的奇数次

2021年5月8日16:23:57 发表评论 808 次浏览

本文概述

给定一个正整数数组。除一个数字为奇数次外, 所有数字均出现偶数次。在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

请参考完整的文章查找出现次数的奇数更多细节!

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: