给定一个数组，其中每个元素出现三次，只有一个元素只出现一次。找到发生一次的元素。预期的时间复杂度为O（n）和O（1）额外空间。
null
例如：
输入： arr[]={12,1,12,3,12,1,1,2,3,3} 输出： 2. 在给定的数组中，除2出现一次外，所有元素都出现三次。
输入： arr[]={10,20,10,30,10,30,30} 输出： 20 在给定的数组中，除了出现一次的20之外，所有元素都出现三次。
我们可以使用排序在O（nLogn）时间内完成。我们也可以使用哈希，它的最坏时间复杂度为O（n），但需要额外的空间。 其思想是对一个时间为O（n）且使用O（1）额外空间的解决方案使用位运算符。这个解决方案不像其他基于XOR的解决方案那样简单，因为所有元素在这里出现的次数都是奇数。这个想法来源于 在这里 . 对数组中的所有元素运行循环。在每次迭代结束时，保持以下两个值。 其中： 第1次、第4次或第7次出现的位。。等 两个： 第二次、第五次或第八次出现的位。。等 最后，我们返回’one’的值 如何保持“一”和“二”的价值观？ “一”和“二”被初始化为0。对于数组中的每个新元素，找出新元素中的公共设置位和之前的“一”值。这些公共设置位实际上是应该添加到“two”中的位。用“2”对公共集合位进行按位异或Two’也会得到一些第三次出现的额外比特。这些额外的位稍后会被删除。 通过对新元素进行异或操作，将之前的值“one”更新为“one”。可能有一些位第三次出现。这些额外的位稍后也会被删除。 “一”和“二”都包含第三次出现的额外位。通过找出“一”和“二”中的公共设置位来删除这些额外位。
以下是上述方法的实施情况：
C++
// C++ program to find the element // that occur only once #include <bits/stdc++.h> using namespace std; int getSingle( int arr[], int n) { int ones = 0, twos = 0; int common_bit_mask; // Let us take the example of // {3, 3, 2, 3} to understand // this for ( int i = 0; i < n; i++) { /* The expression "one & arr[i]" gives the bits that are there in both 'ones' and new element from arr[]. We add these bits to 'twos' using bitwise OR Value of 'twos' will be set as 0, 3, 3 and 1 after 1st, 2nd, 3rd and 4th iterations respectively */ twos = twos | (ones & arr[i]); /* XOR the new bits with previous 'ones' to get all bits appearing odd number of times Value of 'ones' will be set as 3, 0, 2 and 3 after 1st, 2nd, 3rd and 4th iterations respectively */ ones = ones ^ arr[i]; /* The common bits are those bits which appear third time So these bits should not be there in both 'ones' and 'twos'. common_bit_mask contains all these bits as 0, so that the bits can be removed from 'ones' and 'twos' Value of 'common_bit_mask' will be set as 00, 00, 01 and 10 after 1st, 2nd, 3rd and 4th iterations respectively */ common_bit_mask = ~(ones & twos); /* Remove common bits (the bits that appear third time) from 'ones' Value of 'ones' will be set as 3, 0, 0 and 2 after 1st, 2nd, 3rd and 4th iterations respectively */ ones &= common_bit_mask; /* Remove common bits (the bits that appear third time) from 'twos' Value of 'twos' will be set as 0, 3, 1 and 0 after 1st, 2nd, 3rd and 4th iterations respectively */ twos &= common_bit_mask; // uncomment this code to see intermediate values // printf (" %d %d n", ones, twos); } return ones; } // Driver code int main() { int arr[] = { 3, 3, 2, 3 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "The element with single occurrence is " << getSingle(arr, n); return 0; } // This code is contributed by rathbhupendra |
C
// C program to find the element // that occur only once #include <stdio.h> int getSingle( int arr[], int n) { int ones = 0, twos = 0; int common_bit_mask; // Let us take the example of {3, 3, 2, 3} to understand this for ( int i = 0; i < n; i++) { /* The expression "one & arr[i]" gives the bits that are there in both 'ones' and new element from arr[]. We add these bits to 'twos' using bitwise OR Value of 'twos' will be set as 0, 3, 3 and 1 after 1st, 2nd, 3rd and 4th iterations respectively */ twos = twos | (ones & arr[i]); /* XOR the new bits with previous 'ones' to get all bits appearing odd number of times Value of 'ones' will be set as 3, 0, 2 and 3 after 1st, 2nd, 3rd and 4th iterations respectively */ ones = ones ^ arr[i]; /* The common bits are those bits which appear third time So these bits should not be there in both 'ones' and 'twos'. common_bit_mask contains all these bits as 0, so that the bits can be removed from 'ones' and 'twos' Value of 'common_bit_mask' will be set as 00, 00, 01 and 10 after 1st, 2nd, 3rd and 4th iterations respectively */ common_bit_mask = ~(ones & twos); /* Remove common bits (the bits that appear third time) from 'ones' Value of 'ones' will be set as 3, 0, 0 and 2 after 1st, 2nd, 3rd and 4th iterations respectively */ ones &= common_bit_mask; /* Remove common bits (the bits that appear third time) from 'twos' Value of 'twos' will be set as 0, 3, 1 and 0 after 1st, 2nd, 3rd and 4th iterations respectively */ twos &= common_bit_mask; // uncomment this code to see intermediate values // printf (" %d %d n", ones, twos); } return ones; } int main() { int arr[] = { 3, 3, 2, 3 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "The element with single occurrence is %d " , getSingle(arr, n)); return 0; } |
JAVA
// Java code to find the element // that occur only once class GFG { // Method to find the element that occur only once static int getSingle( int arr[], int n) { int ones = 0 , twos = 0 ; int common_bit_mask; for ( int i = 0 ; i < n; i++) { /*"one & arr[i]" gives the bits that are there in both 'ones' and new element from arr[]. We add these bits to 'twos' using bitwise OR*/ twos = twos | (ones & arr[i]); /*"one & arr[i]" gives the bits that are there in both 'ones' and new element from arr[]. We add these bits to 'twos' using bitwise OR*/ ones = ones ^ arr[i]; /* The common bits are those bits which appear third time So these bits should not be there in both 'ones' and 'twos'. common_bit_mask contains all these bits as 0, so that the bits can be removed from 'ones' and 'twos'*/ common_bit_mask = ~(ones & twos); /*Remove common bits (the bits that appear third time) from 'ones'*/ ones &= common_bit_mask; /*Remove common bits (the bits that appear third time) from 'twos'*/ twos &= common_bit_mask; } return ones; } // Driver method public static void main(String args[]) { int arr[] = { 3 , 3 , 2 , 3 }; int n = arr.length; System.out.println( "The element with single occurrence is " + getSingle(arr, n)); } } // Code contributed by Rishab Jain |
Python3
# Python3 code to find the element that # appears once def getSingle(arr, n): ones = 0 twos = 0 for i in range (n): # one & arr[i]" gives the bits that # are there in both 'ones' and new # element from arr[]. We add these # bits to 'twos' using bitwise XOR twos = twos ^ (ones & arr[i]) # one & arr[i]" gives the bits that # are there in both 'ones' and new # element from arr[]. We add these # bits to 'twos' using bitwise XOR ones = ones ^ arr[i] # The common bits are those bits # which appear third time. So these # bits should not be there in both # 'ones' and 'twos'. common_bit_mask # contains all these bits as 0, so # that the bits can be removed from # 'ones' and 'twos' common_bit_mask = ~(ones & twos) # Remove common bits (the bits that # appear third time) from 'ones' ones & = common_bit_mask # Remove common bits (the bits that # appear third time) from 'twos' twos & = common_bit_mask return ones # driver code arr = [ 3 , 3 , 2 , 3 ] n = len (arr) print ( "The element with single occurrence is " , getSingle(arr, n)) # This code is contributed by "Abhishek Sharma 44" |
C#
// C# code to find the element // that occur only once using System; class GFG { // Method to find the element // that occur only once static int getSingle( int [] arr, int n) { int ones = 0, twos = 0; int common_bit_mask; for ( int i = 0; i < n; i++) { // "one & arr[i]" gives the bits // that are there in both 'ones' // and new element from arr[]. // We add these bits to 'twos' // using bitwise OR twos = twos | (ones & arr[i]); // "one & arr[i]" gives the bits // that are there in both 'ones' // and new element from arr[]. // We add these bits to 'twos' // using bitwise OR ones = ones ^ arr[i]; // The common bits are those bits // which appear third time So these // bits should not be there in both // 'ones' and 'twos'. common_bit_mask // contains all these bits as 0, // so that the bits can be removed // from 'ones' and 'twos' common_bit_mask = ~(ones & twos); // Remove common bits (the bits that // appear third time) from 'ones' ones &= common_bit_mask; // Remove common bits (the bits that // appear third time) from 'twos' twos &= common_bit_mask; } return ones; } // Driver code public static void Main() { int [] arr = { 3, 3, 2, 3 }; int n = arr.Length; Console.WriteLine( "The element with single" + "occurrence is " + getSingle(arr, n)); } } // This Code is contributed by vt_m. |
PHP
<?php // PHP program to find the element // that occur only once function getSingle( $arr , $n ) { $ones = 0; $twos = 0 ; $common_bit_mask ; // Let us take the example of // {3, 3, 2, 3} to understand this for ( $i = 0; $i < $n ; $i ++ ) { /* The expression "one & arr[i]" gives the bits that are there in both 'ones' and new element from arr[]. We add these bits to 'twos' using bitwise OR Value of 'twos' will be set as 0, 3, 3 and 1 after 1st, 2nd, 3rd and 4th iterations respectively */ $twos = $twos | ( $ones & $arr [ $i ]); /* XOR the new bits with previous 'ones' to get all bits appearing odd number of times Value of 'ones' will be set as 3, 0, 2 and 3 after 1st, 2nd, 3rd and 4th iterations respectively */ $ones = $ones ^ $arr [ $i ]; /* The common bits are those bits which appear third time. So these bits should not be there in both 'ones' and 'twos'. common_bit_mask contains all these bits as 0, so that the bits can be removed from 'ones' and 'twos' Value of 'common_bit_mask' will be set as 00, 00, 01 and 10 after 1st, 2nd, 3rd and 4th iterations respectively */ $common_bit_mask = ~( $ones & $twos ); /* Remove common bits (the bits that appear third time) from 'ones' Value of 'ones' will be set as 3, 0, 0 and 2 after 1st, 2nd, 3rd and 4th iterations respectively */ $ones &= $common_bit_mask ; /* Remove common bits (the bits that appear third time) from 'twos' Value of 'twos' will be set as 0, 3, 1 and 0 after 1st, 2nd, 3rd and 4th iterations respectively */ $twos &= $common_bit_mask ; // uncomment this code to see // intermediate values // printf (" %d %d n", ones, twos); } return $ones ; } // Driver Code $arr = array (3, 3, 2, 3); $n = sizeof( $arr ); echo "The element with single " . "occurrence is " , getSingle( $arr , $n ); // This code is contributed by m_kit ?> |
Javascript
<script> // Javascript program for the above approach // Method to find the element that occur only once function getSingle(arr, n) { let ones = 0, twos = 0; let common_bit_mask; for (let i = 0; i < n; i++) { /*"one & arr[i]" gives the bits that are there in both 'ones' and new element from arr[]. We add these bits to 'twos' using bitwise OR*/ twos = twos | (ones & arr[i]); /*"one & arr[i]" gives the bits that are there in both 'ones' and new element from arr[]. We add these bits to 'twos' using bitwise OR*/ ones = ones ^ arr[i]; /* The common bits are those bits which appear third time So these bits should not be there in both 'ones' and 'twos'. common_bit_mask contains all these bits as 0, so that the bits can be removed from 'ones' and 'twos'*/ common_bit_mask = ~(ones & twos); /*Remove common bits (the bits that appear third time) from 'ones'*/ ones &= common_bit_mask; /*Remove common bits (the bits that appear third time) from 'twos'*/ twos &= common_bit_mask; } return ones; } // Driver Code let arr = [ 3, 3, 2, 3 ]; let n = arr.length; document.write( "The element with single occurrence is " + getSingle(arr, n)); </script> |
输出
The element with single occurrence is 2
时间复杂性： O（n） 辅助空间： O（1）
下面是另一个O（n）时间复杂度和O（1）额外空间方法，由 aj .我们可以对所有数字的相同位置的位求和，取3的模。总和不是3的倍数的位是单次出现的数字位。 让我们考虑示例数组{ 5, 5, 5，8 }。101，101，101，1000 第一位的总和%3=（1+1+1+0）%3=0； 第二位的总和%3=（0+0+0+0）%3=0； 第三位的总和%3=（1+1+1+0）%3=0； 第四位的总和%3=（1）%3=1； 所以一次出现的数字是1000
注： 这种方法不适用于负数
以下是上述方法的实施情况：
C++
// C++ program to find the element // that occur only once #include <bits/stdc++.h> using namespace std; #define INT_SIZE 32 int getSingle( int arr[], int n) { // Initialize result int result = 0; int x, sum; // Iterate through every bit for ( int i = 0; i < INT_SIZE; i++) { // Find sum of set bits at ith position in all // array elements sum = 0; x = (1 << i); for ( int j = 0; j < n; j++) { if (arr[j] & x) sum++; } // The bits with sum not multiple of 3, are the // bits of element with single occurrence. if ((sum % 3) != 0) result |= x; } return result; } // Driver code int main() { int arr[] = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "The element with single occurrence is " << getSingle(arr, n); return 0; } // This code is contributed by rathbhupendra |
C
// C program to find the element // that occur only once #include <stdio.h> #define INT_SIZE 32 int getSingle( int arr[], int n) { // Initialize result int result = 0; int x, sum; // Iterate through every bit for ( int i = 0; i < INT_SIZE; i++) { // Find sum of set bits at ith position in all // array elements sum = 0; x = (1 << i); for ( int j = 0; j < n; j++) { if (arr[j] & x) sum++; } // The bits with sum not multiple of 3, are the // bits of element with single occurrence. if ((sum % 3) != 0) result |= x; } return result; } // Driver program to test above function int main() { int arr[] = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "The element with single occurrence is %d " , getSingle(arr, n)); return 0; } |
JAVA
// Java code to find the element // that occur only once class GFG { static final int INT_SIZE = 32 ; // Method to find the element that occur only once static int getSingle( int arr[], int n) { int result = 0 ; int x, sum; // Iterate through every bit for ( int i = 0 ; i < INT_SIZE; i++) { // Find sum of set bits at ith position in all // array elements sum = 0 ; x = ( 1 << i); for ( int j = 0 ; j < n; j++) { if ((arr[j] & x) != 0 ) sum++; } // The bits with sum not multiple of 3, are the // bits of element with single occurrence. if ((sum % 3 ) != 0 ) result |= x; } return result; } // Driver method public static void main(String args[]) { int arr[] = { 12 , 1 , 12 , 3 , 12 , 1 , 1 , 2 , 3 , 2 , 2 , 3 , 7 }; int n = arr.length; System.out.println( "The element with single occurrence is " + getSingle(arr, n)); } } // Code contributed by Rishab Jain |
Python3
# Python3 code to find the element # that occur only once INT_SIZE = 32 def getSingle(arr, n) : # Initialize result result = 0 # Iterate through every bit for i in range ( 0 , INT_SIZE) : # Find sum of set bits # at ith position in all # array elements sm = 0 x = ( 1 << i) for j in range ( 0 , n) : if (arr[j] & x) : sm = sm + 1 # The bits with sum not # multiple of 3, are the # bits of element with # single occurrence. if ((sm % 3 )! = 0 ) : result = result | x return result # Driver program arr = [ 12 , 1 , 12 , 3 , 12 , 1 , 1 , 2 , 3 , 2 , 2 , 3 , 7 ] n = len (arr) print ( "The element with single occurrence is " , getSingle(arr, n)) # This code is contributed # by Nikita Tiwari. |
C#
// C# code to find the element // that occur only once using System; class GFG { static int INT_SIZE = 32; // Method to find the element // that occur only once static int getSingle( int [] arr, int n) { int result = 0; int x, sum; // Iterate through every bit for ( int i = 0; i < INT_SIZE; i++) { // Find sum of set bits at ith // position in all array elements sum = 0; x = (1 << i); for ( int j = 0; j < n; j++) { if ((arr[j] & x) != 0) sum++; } // The bits with sum not multiple // of 3, are the bits of element // with single occurrence. if ((sum % 3) != 0) result |= x; } return result; } // Driver Code public static void Main() { int [] arr = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 }; int n = arr.Length; Console.WriteLine( "The element with single " + "occurrence is " + getSingle(arr, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP code to find the element // that occur only once $INT_SIZE = 32; function getSingle( $arr , $n ) { global $INT_SIZE ; // Initialize result $result = 0; $x ; $sum ; // Iterate through every bit for ( $i = 0; $i < $INT_SIZE ; $i ++) { // Find sum of set bits at ith // position in all array elements $sum = 0; $x = (1 << $i ); for ( $j = 0; $j < $n ; $j ++ ) { if ( $arr [ $j ] & $x ) $sum ++; } // The bits with sum not multiple // of 3, are the bits of element // with single occurrence. if (( $sum % 3) !=0 ) $result |= $x ; } return $result ; } // Driver Code $arr = array (12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7); $n = sizeof( $arr ); echo "The element with single occurrence is " , getSingle( $arr , $n ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to find the element // that occur only once let INT_SIZE = 32; function getSingle(arr, n) { // Initialize result let result = 0; let x, sum; // Iterate through every bit for (let i = 0; i < INT_SIZE; i++) { // Find sum of set bits at ith position in all // array elements sum = 0; x = (1 << i); for (let j = 0; j < n; j++) { if (arr[j] & x) sum++; } // The bits with sum not multiple of 3, are the // bits of element with single occurrence. if ((sum % 3) != 0) result |= x; } return result; } // Driver code let arr = [ 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 ]; let n = arr.length; document.write( "The element with single occurrence is " + getSingle(arr, n)); // This code is contributed by mukesh07. </script> |
输出
The element with single occurrence is 7
时间复杂性： O（n）
辅助空间： O（1）
另一种方法是 阿披实·沙玛44 .将每个数字相加一次，然后将总和乘以3，我们将得到数组中每个元素总和的三倍。将其存储为三次总和。从三次和中减去整个数组的和，并将结果除以2。我们得到的数字是所需的数字（在数组中出现一次）。
数组[]：[a，a，a，b，b，b，c，c，d] 数学方程=（3*（a+b+c+d）–（a+a+a+b+b+b+c+c+d））/2 用更简单的话来说：（3*（不带重复项的数组的和）–（数组的和））/2
let arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}Required no = ( 3*(sum_of_array_without_duplicates) - (sum_of_array) ) / 2 = ( 3*(12 + 1 + 3 + 2) - (12 + 1 + 12 + 3 + 12 + 1 + 1 + 2 + 3 + 3))/2 = ( 3* 18 - 50) / 2 = (54 - 50) / 2 = 2 (required answer)
正如我们所知 设置 不包含任何重复元素， 但是，std:：set通常被实现为红黑二叉搜索树。当树保持平衡时，在这个数据结构上的插入具有O（log（n））复杂性的最坏情况。我们将使用 设置 在这里
以下是上述方法的实施情况：
C++
// C++ program to find the element // that occur only once #include <bits/stdc++.h> using namespace std; // function which find number int singleNumber( int a[], int n) { unordered_set< int > s(a, a + n); int arr_sum = accumulate(a, a + n, 0); // sum of array int set_sum = accumulate(s.begin(), s.end(), 0); // sum of set // applying the formula. return (3 * set_sum - arr_sum) / 2; } // driver function int main() { int a[] = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 }; int n = sizeof (a) / sizeof (a[0]); cout << "The element with single occurrence is " << singleNumber(a, n); } // This code is contributed by Mohit Kumar 29 (IIIT gwalior) |
JAVA
// Java program to find the element // that occur only once import java.util.*; class GFG { // function which find number static int singleNumber( int a[], int n) { HashSet<Integer> s = new HashSet<Integer>(); for ( int i : a) { s.add(i); } int arr_sum = 0 ; // sum of array for ( int i : a) { arr_sum += i; } int set_sum = 0 ; // sum of set for ( int i : s) { set_sum += i; } // applying the formula. return ( 3 * set_sum - arr_sum) / 2 ; } // Driver code public static void main(String[] args) { int a[] = { 12 , 1 , 12 , 3 , 12 , 1 , 1 , 2 , 3 , 2 , 2 , 3 , 7 }; int n = a.length; System.out.println( "The element with single " + "occurrence is " + singleNumber(a, n)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the element # that occur only once # function which find number def singleNumber(nums): # applying the formula. return ( 3 * sum ( set (nums)) - sum (nums)) / 2 # driver function. a = [ 12 , 1 , 12 , 3 , 12 , 1 , 1 , 2 , 3 , 2 , 2 , 3 , 7 ] print ( "The element with single occurrence is " , int (singleNumber(a))) |
C#
// C# program to find the element // that occur only once using System; using System.Collections.Generic; class GFG { // function which find number static int singleNumber( int [] a, int n) { HashSet< int > s = new HashSet< int >(); foreach ( int i in a) { s.Add(i); } int arr_sum = 0; // sum of array foreach ( int i in a) { arr_sum += i; } int set_sum = 0; // sum of set foreach ( int i in s) { set_sum += i; } // applying the formula. return (3 * set_sum - arr_sum) / 2; } // Driver code public static void Main(String[] args) { int [] a = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 }; int n = a.Length; Console.WriteLine( "The element with single " + "occurrence is " + singleNumber(a, n)); } } // This code is contributed by PrinciRaj1992 |
PHP
<?php // PHP program to find the element // that occur only once //function which find number function singleNumber( $a , $n ) { $s = array (); for ( $i = 0; $i < count ( $a ); $i ++) array_push ( $s , $a [ $i ]); $s = array_values ( array_unique ( $s )); $arr_sum = 0; // sum of array for ( $i = 0; $i < count ( $a ); $i ++) { $arr_sum += $a [ $i ]; } $set_sum = 0; // sum of set for ( $i = 0; $i < count ( $s ); $i ++) { $set_sum += $s [ $i ]; } // applying the formula. return (int)(((3 * $set_sum ) - $arr_sum ) / 2); } // Driver code $a = array (12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7); $n = count ( $a ); print ( "The element with single occurrence is " . singleNumber( $a , $n )); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to find the element // that occur only once // function which find number function singleNumber(a,n) { let s = new Set(a); let arr_sum = 0; // sum of array for (let i=0;i<a.length;i++) { arr_sum += a[i]; } let set_sum = 0; // sum of set for (let i of s) { set_sum +=i; } // applying the formula. return Math.floor((3 * set_sum - arr_sum) / 2); } // Driver code let arr=[12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 ]; let n = arr.length; document.write( "The element with single " + "occurrence is " + singleNumber(arr, n)); // This code is contributed by unknown2108 </script> |
输出
The element with single occurrence is 7
时间复杂性： O（Nlog（N）） 辅助空间： O（N）
方法4：使用Counter（）函数
- 利用计数器函数计算阵列频率
- 遍历此计数器字典并检查是否有任何键的值为1
- 如果任何键的值为1，则返回该键
以下是实施情况：
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // function which find number int singlenumber( int a[], int N) { // umap for finding frequency unordered_map< int , int >fmap; // traverse the array for frequency for ( int i = 0; i < N;i++) { fmap[a[i]]++; } // iterate over the map for ( auto it:fmap) { // check frequency whether it is one or not. if (it.second == 1) { // return it as we got the answer return it.first; } } } // Driver code int main() { // given array int a[]={12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7}; // size of the array int N= sizeof (a)/ sizeof (a[0]); // printing the returned value cout << singlenumber(a,N); return 0; } // This Code is contributed by // Murarishetty Santhosh Charan |
JAVA
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // function which find number static int singlenumber( int a[], int N) { // umap for finding frequency Map<Integer, Integer> fmap = new HashMap<Integer, Integer>(); // traverse the array for frequency for ( int i = 0 ; i < N;i++) { if (!fmap.containsKey(a[i])) fmap.put(a[i], 0 ); fmap.put(a[i],fmap.get(a[i])+ 1 ); } // iterate over the map for (Map.Entry<Integer, Integer> me : fmap.entrySet()) { // check frequency whether it is one or not. if (me.getValue()== 1 ) { // return it as we got the answer return me.getKey(); } } return - 1 ; } // Driver code public static void main (String[] args) { // given array int a[]={ 12 , 1 , 12 , 3 , 12 , 1 , 1 , 2 , 3 , 2 , 2 , 3 , 7 }; // size of the array int N= a.length; // printing the returned value System.out.println( "The element with single occurrence is " +singlenumber(a,N)); } } // This code is contributed by avanitrachhadiya2155 |
Python3
from collections import Counter # Python3 program to find the element # that occur only once # function which find number def singleNumber(nums): # storing the frequencies using Counter freq = Counter(nums) # traversing the Counter dictionary for i in freq: # check if any value is 1 if (freq[i] = = 1 ): return i # driver function. a = [ 12 , 1 , 12 , 3 , 12 , 1 , 1 , 2 , 3 , 2 , 2 , 3 , 7 ] print ( "The element with single occurrence is " , int (singleNumber(a))) # This code is contributed by vikkycirus |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; public class GFG { // function which find number static void singlenumber( int [] a, int N) { // umap for finding frequency Dictionary< int , int > fmap = new Dictionary< int , int >(); // traverse the array for frequency for ( int i = 0; i < N; i++) { if (fmap.ContainsKey(a[i])) fmap[a[i]]++; else fmap.Add(a[i], 1); } // iterate over the map foreach ( int it in fmap.Keys.ToList()) { // check frequency whether it is one or not. if (fmap[it] == 1) { // return it as we got the answer Console.Write( "The element with single occurrence is " + it); } } } // Driver Code public static void Main ( string [] args) { // given array int [] arr = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7}; // size of the array int n= arr.Length; // printing the returned value singlenumber(arr, n); } } // This code is contributed by splevel62. |
Javascript
<script> // Javascript program for the above approach // function which find number function singlenumber(a,N) { // umap for finding frequency let fmap= new Map(); // traverse the array for frequency for (let i = 0; i < N;i++) { if (!fmap.has(a[i])) fmap.set(a[i],0); fmap.set(a[i],fmap.get(a[i])+1); } // iterate over the map for (let [key, value] of fmap.entries()) { // check frequency whether it is one or not. if (value==1) { // return it as we got the answer return key; } } } // Driver code // given array let a = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]; // size of the array let N = a.length; // printing the returned value document.write( "The element with single occurrence is " +singlenumber(a,N)); // This code is contributed by rag2127 </script> |
输出
The element with single occurrence is 7
时间复杂性： O（n）
辅助空间： O（n）
本文由 苏米特·贾因 并由Geeksforgeks团队审核。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
