找出发生奇数次的次数-yiteyi-C++库

给定一个正整数数组。所有数字出现的次数都是偶数，只有一个数字出现的次数是奇数。在O（n）时间和常数空间中找到数字。

null

例如：

Input : arr = {1, 2, 3, 2, 3, 1, 3}Output : 3Input : arr = {5, 7, 2, 7, 5, 2, 5}Output : 5

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 就是运行两个嵌套循环。外部循环逐个拾取所有元素，内部循环统计外部循环拾取的元素的出现次数。该解的时间复杂度为O（n） ^2. ).

以下是暴力方法的实施：

C++

                         // C++ program to find the element                       
                         // occurring odd number of times                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find the element                       
                         // occurring odd number of times                       
                         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                       
                         int                                     main()                       
                                                 {                       
                                                 int                                     arr[] = { 2, 3, 5, 4, 5, 2,                       
                                                 4, 3, 5, 2, 4, 4, 2 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 // Function calling                       
                                                 cout << getOddOccurrence(arr, n);                       
           
                                                 return                                     0;                       
                                                 }                       

JAVA

                         // Java program to find the element occurring                       
                         // odd number of times                       
                         class                                     OddOccurrence {                       
                                   
                                                 // function to find the element occurring odd                       
                                                 // number of times                       
                                                 static                                     int                                     getOddOccurrence(                                     int                                     arr[],                                     int                                     arr_size)                       
                                                 {                       
                                                 int                                     i;                       
                                                 for                                     (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(String[] args)                       
                                                 {                       
                                                 int                                     arr[] =                                     new                                     int                                     []{                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     4                                     ,                                     2                                     };                       
                                                 int                                     n = arr.length;                       
                                                 System.out.println(getOddOccurrence(arr, n));                       
                                                 }                       
                         }                       
                         // This code has been contributed by Kamal Rawal                       

蟒蛇3

                         # Python program to find the element occurring                       
                         # odd number of times                       
                                   
                         # function to find the element occurring odd                       
                         # number of times                       
                         def                                     getOddOccurrence(arr, arr_size):                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,arr_size):                       
                                                 count                                     =                                     0                       
                                                 for                                     j                                     in                                     range                                     (                                     0                                     , arr_size):                       
                                                 if                                     arr[i]                                     =                                     =                                     arr[j]:                       
                                                 count                                     +                                     =                                     1                       
                                   
                                                 if                                     (count                                     %                                     2                                     !                                     =                                     0                                     ):                       
                                                 return                                     arr[i]                       
                                   
                                                 return                                     -                                     1                       
                                   
                                   
                         # driver code                       
                         arr                                     =                                     [                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     4                                     ,                                     2                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (getOddOccurrence(arr, n))                       
           
                         # This code has been contributed by                       
                         # Smitha Dinesh Semwal                       

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                       

PHP

                         <?php                       
                         // PHP program to find the                       
                         // element occurring odd                       
                         // number of times                       
           
                         // Function to find the element                       
                         // occurring odd number of times                       
                         function                                     getOddOccurrence(&                                     $arr                                     ,                                     $arr_size                                     )                       
                         {                       
                                                 $count                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                       
                                                 $i                                     <                                     $arr_size                                     ;                                     $i                                     ++)                       
                                                 {                       
                                   
                                                 for                                     (                                     $j                                     = 0;                       
                                                 $j                                     <                                     $arr_size                                     ;                                     $j                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $arr                                     [                                     $i                                     ] ==                                     $arr                                     [                                     $j                                     ])                       
                                                 $count                                     ++;                       
                                                 }                       
                                                 if                                     (                                     $count                                     % 2 != 0)                       
                                                 return                                     $arr                                     [                                     $i                                     ];                       
                                                 }                       
                                                 return                                     -1;                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     (2, 3, 5, 4, 5, 2,                       
                                                 4, 3, 5, 2, 4, 4, 2);                       
                         $n                                     = sizeof(                                     $arr                                     );                       
           
                         // Function calling                       
                         echo                                     (getOddOccurrence(                                     $arr                                     ,                                     $n                                     ));                       
           
                         // This code is contributed                       
                         // by Shivi_Aggarwal                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find the element                       
                         // occurring odd number of times                       
           
                         // Function to find the element                       
                         // occurring odd number of times                       
                         function                                     getOddOccurrence(arr, arr_size)                       
                         {                       
                                                 for                                     (let i = 0; i < arr_size; i++) {                       
                                   
                                                 let count = 0;                       
                                   
                                                 for                                     (let j = 0; j < arr_size; j++)                       
                                                 {                       
                                                 if                                     (arr[i] == arr[j])                       
                                                 count++;                       
                                                 }                       
                                                 if                                     (count % 2 != 0)                       
                                                 return                                     arr[i];                       
                                                 }                       
                                                 return                                     -1;                       
                         }                       
           
                         // driver code                       
           
                                                 let arr = [ 2, 3, 5, 4, 5, 2,                       
                                                 4, 3, 5, 2, 4, 4, 2 ];                       
                                                 let n = arr.length;                       
           
                                                 // Function calling                       
                                                 document.write(getOddOccurrence(arr, n));                       
           
                         // This code is contributed by Mayank Tyagi                       
           
                         </script>                       

输出：

时间复杂性： O（n^2）

辅助空间： O（1）

A. 更好的解决方案 就是使用散列。将数组元素用作键，并将其计数用作值。创建一个空哈希表。逐个遍历给定的数组元素并存储计数。该解的时间复杂度为O（n）。但它需要额外的空间进行散列。

节目：

C++

                         // C++ program to find the element                       
                         // occurring odd number of times                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to find the element                       
                         // occurring odd number of times                       
                         int                                     getOddOccurrence(                                     int                                     arr[],                                     int                                     size)                       
                         {                       
                                   
                                                 // Defining HashMap in C++                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > hash;                       
           
                                                 // Putting all elements into the HashMap                       
                                                 for                                     (                                     int                                     i = 0; i < size; i++)                       
                                                 {                       
                                                 hash[arr[i]]++;                       
                                                 }                       
                                                 // Iterate through HashMap to check an element                       
                                                 // occurring odd number of times and return it                       
                                                 for                                     (                                     auto                                     i : hash)                       
                                                 {                       
                                                 if                                     (i.second % 2 != 0)                       
                                                 {                       
                                                 return                                     i.first;                       
                                                 }                       
                                                 }                       
                                                 return                                     -1;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 2, 3, 5, 4, 5, 2, 4,                       
                                                 3, 5, 2, 4, 4, 2 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                   
                                                 // Function calling                       
                                                 cout << getOddOccurrence(arr, n);                       
           
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by codeMan_d.                       

JAVA

                         // Java program to find the element occurring odd                       
                         // number of times                       
                         import                                     java.io.*;                       
                         import                                     java.util.HashMap;                       
           
                         class                                     OddOccurrence                       
                         {                       
                                                 // function to find the element occurring odd                       
                                                 // number of times                       
                                                 static                                     int                                     getOddOccurrence(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 HashMap<Integer,Integer> hmap =                                     new                                     HashMap<>();                       
                                   
                                                 // Putting all elements into the HashMap                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 if                                     (hmap.containsKey(arr[i]))                       
                                                 {                       
                                                 int                                     val = hmap.get(arr[i]);                       
                                   
                                                 // If array element is already present then                       
                                                 // increase the count of that element.                       
                                                 hmap.put(arr[i], val +                                     1                                     );                       
                                                 }                       
                                                 else                       
                                   
                                                 // if array element is not present then put                       
                                                 // element into the HashMap and initialize                       
                                                 // the count to one.                       
                                                 hmap.put(arr[i],                                     1                                     );                       
                                                 }                       
           
                                                 // Checking for odd occurrence of each element present                       
                                                 // in the HashMap                       
                                                 for                                     (Integer a:hmap.keySet())                       
                                                 {                       
                                                 if                                     (hmap.get(a) %                                     2                                     !=                                     0                                     )                       
                                                 return                                     a;                       
                                                 }                       
                                                 return                                     -                                     1                                     ;                       
                                                 }                       
                                   
                                                 // driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] =                                     new                                     int                                     []{                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     4                                     ,                                     2                                     };                       
                                                 int                                     n = arr.length;                       
                                                 System.out.println(getOddOccurrence(arr, n));                       
                                                 }                       
                         }                       
                         // This code is contributed by Kamal Rawal                       

蟒蛇3

                         # Python3 program to find the element                       
                         # occurring odd number of times                       
                                   
                         # function to find the element                       
                         # occurring odd number of times                       
                         def                                     getOddOccurrence(arr,size):                       
                                   
                                                 # Defining HashMap in C++                       
                                                 Hash                                     =                                     dict                                     ()                       
                                   
                                                 # Putting all elements into the HashMap                       
                                                 for                                     i                                     in                                     range                                     (size):                       
                                                 Hash                                     [arr[i]]                                     =                                     Hash                                     .get(arr[i],                                     0                                     )                                     +                                     1                                     ;                       
                                   
                                                 # Iterate through HashMap to check an element                       
                                                 # occurring odd number of times and return it                       
                                                 for                                     i                                     in                                     Hash                                     :                       
           
                                                 if                                     (                                     Hash                                     [i]                                     %                                     2                                     !                                     =                                     0                                     ):                       
                                                 return                                     i                       
                                                 return                                     -                                     1                       
           
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     4                                     ,                                     2                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                                   
                         # Function calling                       
                         print                                     (getOddOccurrence(arr, n))                       
           
                         # This code is contributed by mohit kumar                       

C#

                         // C# program to find the element occurring odd                       
                         // number of times                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         public                                     class                                     OddOccurrence                       
                         {                       
                                                 // function to find the element occurring odd                       
                                                 // number of times                       
                                                 static                                     int                                     getOddOccurrence(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 Dictionary<                                     int                                     ,                                     int                                     > hmap =                                     new                                     Dictionary<                                     int                                     ,                                     int                                     >();                       
                                   
                                                 // Putting all elements into the HashMap                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (hmap.ContainsKey(arr[i]))                       
                                                 {                       
                                                 int                                     val = hmap[arr[i]];                       
                                   
                                                 // If array element is already present then                       
                                                 // increase the count of that element.                       
                                                 hmap.Remove(arr[i]);                       
                                                 hmap.Add(arr[i], val + 1);                       
                                                 }                       
                                                 else                       
                                   
                                                 // if array element is not present then put                       
                                                 // element into the HashMap and initialize                       
                                                 // the count to one.                       
                                                 hmap.Add(arr[i], 1);                       
                                                 }                       
           
                                                 // Checking for odd occurrence of each element present                       
                                                 // in the HashMap                       
                                                 foreach                                     (KeyValuePair<                                     int                                     ,                                     int                                     > entry                                     in                                     hmap)                       
                                                 {                       
                                                 if                                     (entry.Value % 2 != 0)                       
                                                 {                       
                                                 return                                     entry.Key;                       
                                                 }                       
                                                 }                       
                                                 return                                     -1;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     []arr =                                     new                                     int                                     []{2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};                       
                                                 int                                     n = arr.Length;                       
                                                 Console.WriteLine(getOddOccurrence(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Princi Singh                       

Javascript

                         <script>                       
                         // Javascript program to find the element occurring odd                       
                         // number of times                       
                                   
                                                 // function to find the element occurring odd                       
                                                 // number of times                       
                                                 function                                     getOddOccurrence(arr,n)                       
                                                 {                       
                                                 let hmap =                                     new                                     Map();                       
                                   
                                                 // Putting all elements into the HashMap                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (hmap.has(arr[i]))                       
                                                 {                       
                                                 let val = hmap.get(arr[i]);                       
                                                 // If array element is already present then                       
                                                 // increase the count of that element.                       
                                                 hmap.set(arr[i], val + 1);                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 // if array element is not present then put                       
                                                 // element into the HashMap and initialize                       
                                                 // the count to one.                       
                                                 hmap.set(arr[i], 1);                       
                                                 }                       
                                                 }                       
                                   
                                   
                                                 // Checking for odd occurrence of each element present                       
                                                 // in the HashMap                       
                                                 for                                     (let [key, value] of hmap.entries())                       
                                                 {                       
                                                 //document.write(hmap[a]+"<br>")                       
                                                 if                                     (hmap.get(key) % 2 != 0)                       
                                                 return                                     key;                       
                                                 }                       
                                                 return                                     -1;                       
                                                 }                       
                                   
                                                 // driver code                       
                                                 let arr=[2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2];                       
                                                 let n = arr.length;                       
                                                 document.write(getOddOccurrence(arr, n));                       
                                   
                                   
                                                 // This code is contributed by unknown2108                       
                         </script>                       

输出：

时间复杂度：O（n）

辅助空间：O（n）

这个 最佳解决方案 就是对所有元素进行位异或运算。所有元素的异或给我们提供奇数出现的元素。请注意，如果两个元素相同，那么两个元素的XOR为0，并且数字x与0的XOR为x。

以下是上述方法的实施情况。

C++

                         // C++ program to find the element                       
                         // occurring odd number of times                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find element occurring                       
                         // odd number of times                       
                         int                                     getOddOccurrence(                                     int                                     ar[],                                     int                                     ar_size)                       
                         {                       
                                                 int                                     res = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < ar_size; i++)                       
                                                 res = res ^ ar[i];                       
                                   
                                                 return                                     res;                       
                         }                       
           
                         /* Driver function to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};                       
                                                 int                                     n =                                     sizeof                                     (ar)/                                     sizeof                                     (ar[0]);                       
                                   
                                                 // Function calling                       
                                                 cout << getOddOccurrence(ar, n);                       
                                   
                                                 return                                     0;                       
                         }                       

C

                         // C program to find the element                       
                         // occurring odd number of times                       
                         #include <stdio.h>                       
           
                         // Function to find element occurring                       
                         // odd number of times                       
                         int                                     getOddOccurrence(                                     int                                     ar[],                                     int                                     ar_size)                       
                         {                       
                                                 int                                     res = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < ar_size; i++)                       
                                                 res = res ^ ar[i];                       
                                   
                                                 return                                     res;                       
                         }                       
           
                         /* Driver function to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};                       
                                                 int                                     n =                                     sizeof                                     (ar) /                                     sizeof                                     (ar[0]);                       
                                   
                                                 // Function calling                       
                                                 printf                                     (                                     "%d"                                     , getOddOccurrence(ar, n));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         //Java program to find the element occurring odd number of times                       
           
                         class                                     OddOccurance                       
                         {                       
                                                 int                                     getOddOccurrence(                                     int                                     ar[],                                     int                                     ar_size)                       
                                                 {                       
                                                 int                                     i;                       
                                                 int                                     res =                                     0                                     ;                       
                                                 for                                     (i =                                     0                                     ; i < ar_size; i++)                       
                                                 {                       
                                                 res = res ^ ar[i];                       
                                                 }                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 OddOccurance occur =                                     new                                     OddOccurance();                       
                                                 int                                     ar[] =                                     new                                     int                                     []{                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     4                                     ,                                     2                                     };                       
                                                 int                                     n = ar.length;                       
                                                 System.out.println(occur.getOddOccurrence(ar, n));                       
                                                 }                       
                         }                       
                         // This code has been contributed by Mayank Jaiswal                       

蟒蛇3

                         # Python program to find the element occurring odd number of times                       
           
                         def                                     getOddOccurrence(arr):                       
           
                                                 # Initialize result                       
                                                 res                                     =                                     0                       
                                   
                                                 # Traverse the array                       
                                                 for                                     element                                     in                                     arr:                       
                                                 # XOR with the result                       
                                                 res                                     =                                     res ^ element                       
           
                                                 return                                     res                       
           
                         # Test array                       
                         arr                                     =                                     [                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     ,                                     2                                     ,                                     4                                     ,                                     4                                     ,                                     2                                     ]                       
           
                         print                                     (                                     "%d"                                     %                                     getOddOccurrence(arr))                       

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                       

PHP

                         <?php                       
                         // PHP program to find the                       
                         // element occurring odd                       
                         // number of times                       
           
                         // Function to find element                       
                         // occurring odd number of times                       
                         function                                     getOddOccurrence(&                                     $ar                                     ,                                     $ar_size                                     )                       
                         {                       
                                                 $res                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $ar_size                                     ;                                     $i                                     ++)                       
                                                 $res                                     =                                     $res                                     ^                                     $ar                                     [                                     $i                                     ];                       
                                   
                                                 return                                     $res                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $ar                                     =                                     array                                     (2, 3, 5, 4, 5, 2,                       
                                                 4, 3, 5, 2, 4, 4, 2);                       
                         $n                                     = sizeof(                                     $ar                                     );                       
           
                         // Function calling                       
                         echo                                     (getOddOccurrence(                                     $ar                                     ,                                     $n                                     ));                       
                                   
                         // This code is contributed                       
                         // by Shivi_Aggarwal                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find the element                       
                         // occurring odd number of times                       
           
                         // Function to find the element                       
                         // occurring odd number of times                       
                         function                                     getOddOccurrence( ar, ar_size)                       
                         {                       
                                                 let res = 0;                       
                                   
                                                 for                                     (let i = 0; i < ar_size; i++)                       
                                                 res = res ^ ar[i];                       
                                   
                                                 return                                     res;                       
                         }                       
           
                                                 // driver code                       
           
                                                 let arr = [ 2, 3, 5, 4, 5, 2, 4,                       
                                                 3, 5, 2, 4, 4, 2 ];                       
                                                 let n = arr.length;                       
           
                                                 // Function calling                       
                                                 document.write(getOddOccurrence(arr, n));                       
           
           
                         </script>                       

输出：

时间复杂性： O（n）

辅助空间： O（1）

方法3：使用内置Python函数：

使用柜台作用
频率字典中的遍历
检查哪个元素具有奇数频率。
打印该元素并打破循环

以下是实施情况：

蟒蛇3

                         # importing counter from collections                       
                         from                                     collections                                     import                                     Counter                       
           
                         # Python3 implementation to find                       
                         # odd frequency element                       
                         def                                     oddElement(arr, n):                       
           
                                                 # Calculating frequencies using Counter                       
                                                 count_map                                     =                                     Counter(arr)                       
           
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
           
                                                 # If count of element is odd we return                       
                                                 if                                     (count_map[arr[i]]                                     %                                     2                                     !                                     =                                     0                                     ):                       
                                                 return                                     arr[i]                       
           
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 arr                                     =                                     [                                     1                                     ,                                     1                                     ,                                     3                                     ,                                     3                                     ,                                     5                                     ,                                     6                                     ,                                     6                                     ]                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 print                                     (oddElement(arr, n))                       
           
                         # This code is contributed by vikkycirus                       

输出：

时间复杂性： O（N）

辅助空间： O（1）

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章