给定一个整数数组。除一个数字出现一次外，所有数字都出现两次。在O（n）时间和常数额外空间中查找数字。
null
例子：
Input: ar[] = {7, 3, 5, 4, 5, 3, 4}Output: 7
一种解决方案是检查每个元素是否出现一次。一旦找到一个只出现一次的元素，就返回它。该解的时间复杂度为O（n） 2. ).
更好的解决方案是使用哈希。 1） 遍历所有元素并将它们放入哈希表中。元素用作键，出现次数用作哈希表中的值。 2） 再次遍历数组，并在哈希表中打印计数为1的元素。 此解决方案在O（n）时间内有效，但需要额外的空间。 最好的解决方案是使用XOR。所有数组元素的异或给出了一次出现的数字。这个想法基于以下两个事实。 a） 一个数与其自身的异或为0。 b） 一个数字与0的异或就是数字本身。
Let us consider the above example. Let ^ be xor operator as in C and C++.res = 7 ^ 3 ^ 5 ^ 4 ^ 5 ^ 3 ^ 4Since XOR is associative and commutative, above expression can be written as:res = 7 ^ (3 ^ 3) ^ (4 ^ 4) ^ (5 ^ 5) = 7 ^ 0 ^ 0 ^ 0 = 7 ^ 0 = 7
下面是上述算法的实现。
C++
// C++ program to find the array // element that appears only once #include <iostream> using namespace std; int findSingle( int ar[], int ar_size) { // Do XOR of all elements and return int res = ar[0]; for ( int i = 1; i < ar_size; i++) res = res ^ ar[i]; return res; } // Driver code int main() { int ar[] = {2, 3, 5, 4, 5, 3, 4}; int n = sizeof (ar) / sizeof (ar[0]); cout << "Element occurring once is " << findSingle(ar, n); return 0; } |
JAVA
// Java program to find the array // element that appears only once class MaxSum { // Return the maximum Sum of difference // between consecutive elements. static int findSingle( int ar[], int ar_size) { // Do XOR of all elements and return int res = ar[ 0 ]; for ( int i = 1 ; i < ar_size; i++) res = res ^ ar[i]; return res; } // Driver code public static void main (String[] args) { int ar[] = { 2 , 3 , 5 , 4 , 5 , 3 , 4 }; int n = ar.length; System.out.println( "Element occurring once is " + findSingle(ar, n) + " " ); } } // This code is contributed by Prakriti Gupta |
Python3
# function to find the once # appearing element in array def findSingle( ar, n): res = ar[ 0 ] # Do XOR of all elements and return for i in range ( 1 ,n): res = res ^ ar[i] return res # Driver code ar = [ 2 , 3 , 5 , 4 , 5 , 3 , 4 ] print "Element occurring once is" , findSingle(ar, len (ar)) # This code is contributed by __Devesh Agrawal__ |
C#
// C# program to find the array // element that appears only once using System; class GFG { // Return the maximum Sum of difference // between consecutive elements. static int findSingle( int []ar, int ar_size) { // Do XOR of all elements and return int res = ar[0]; for ( int i = 1; i < ar_size; i++) res = res ^ ar[i]; return res; } // Driver code public static void Main () { int []ar = {2, 3, 5, 4, 5, 3, 4}; int n = ar.Length; Console.Write( "Element occurring once is " + findSingle(ar, n) + " " ); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find the array // element that appears only once function findSingle( $ar , $ar_size ) { // Do XOR of all // elements and return $res = $ar [0]; for ( $i = 1; $i < $ar_size ; $i ++) $res = $res ^ $ar [ $i ]; return $res ; } // Driver code $ar = array (2, 3, 5, 4, 5, 3, 4); $n = count ( $ar ); echo "Element occurring once is " , findSingle( $ar , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript program to find the array // element that appears only once function findSingle(ar, ar_size) { // Do XOR of all elements and return let res = ar[0]; for (let i = 1; i < ar_size; i++) res = res ^ ar[i]; return res; } // Driver code let ar = [2, 3, 5, 4, 5, 3, 4]; let n = ar.length; document.write( "Element occurring once is " + findSingle(ar, n)); // This code is contributed by Surbhi Tyagi </script> |
输出：
Element occurring once is 2
该解决方案的时间复杂度为O（n），需要额外的O（1）个空间。
另一种方法： 这不是一种有效的方法，只是获得预期结果的另一种方法。如果我们将每个数字相加一次，然后将总和乘以2，我们将得到数组中每个元素总和的两倍。然后我们将从两次求和中减去整个数组的和，得到所需的数字（在数组中出现一次）。 数组[]：[a，a，b，b，c，c，d] 数学方程=2*（a+b+c+d）–（a+a+b+b+c+c+d）
简单地说： 2*（无重复项的数组之和）–（数组之和）
let arr[] = {7, 3, 5, 4, 5, 3, 4}Required no = 2*(sum_of_array_without_duplicates) - (sum_of_array) = 2*(7 + 3 + 5 + 4) - (7 + 3 + 5 + 4 + 5 + 3 + 4) = 2* 19 - 31 = 38 - 31 = 7 (required answer)
正如我们所知，集合不包含任何重复元素，我们将使用 设置 在这里
以下是上述方法的实施情况：
C++
// C++ program to find // element that appears once #include <bits/stdc++.h> using namespace std; // function which find number int singleNumber( int nums[], int n) { map< int , int > m; long sum1 = 0,sum2 = 0; for ( int i = 0; i < n; i++) { if (m[nums[i]] == 0) { sum1 += nums[i]; m[nums[i]]++; } sum2 += nums[i]; } // applying the formula. return 2 * (sum1) - sum2; } // Driver code int main() { int a[] = {2, 3, 5, 4, 5, 3, 4}; int n = 7; cout << singleNumber(a,n) << "" ; int b[] = {15, 18, 16, 18, 16, 15, 89}; cout << singleNumber(b,n); return 0; } // This code is contributed by mohit kumar 29 |
JAVA
// Java program to find // element that appears once import java.io.*; import java.util.*; class GFG { // function which find number static int singleNumber( int [] nums, int n) { HashMap<Integer, Integer> m = new HashMap<>(); long sum1 = 0 , sum2 = 0 ; for ( int i = 0 ; i < n; i++) { if (!m.containsKey(nums[i])) { sum1 += nums[i]; m.put(nums[i], 1 ); } sum2 += nums[i]; } // applying the formula. return ( int )( 2 * (sum1) - sum2); } // Driver code public static void main(String args[]) { int [] a = { 2 , 3 , 5 , 4 , 5 , 3 , 4 }; int n = 7 ; System.out.println(singleNumber(a,n)); int [] b = { 15 , 18 , 16 , 18 , 16 , 15 , 89 }; System.out.println(singleNumber(b,n)); } } // This code is contributed by rachana soma |
Python3
# Python3 program to find # element that appears once # function which find number def singleNumber(nums): # applying the formula. return 2 * sum ( set (nums)) - sum (nums) # driver code a = [ 2 , 3 , 5 , 4 , 5 , 3 , 4 ] print ( int (singleNumber(a))) a = [ 15 , 18 , 16 , 18 , 16 , 15 , 89 ] print ( int (singleNumber(a))) # This code is contributed by "Abhishek Sharma 44" |
C#
// C# program to find // element that appears once using System; using System.Collections.Generic; class GFG { // function which find number static int singleNumber( int [] nums, int n) { Dictionary< int , int > m = new Dictionary< int , int >(); long sum1 = 0, sum2 = 0; for ( int i = 0; i < n; i++) { if (!m.ContainsKey(nums[i])) { sum1 += nums[i]; m.Add(nums[i], 1); } sum2 += nums[i]; } // applying the formula. return ( int )(2 * (sum1) - sum2); } // Driver code public static void Main(String []args) { int [] a = {2, 3, 5, 4, 5, 3, 4}; int n = 7; Console.WriteLine(singleNumber(a,n)); int [] b = {15, 18, 16, 18, 16, 15, 89}; Console.WriteLine(singleNumber(b,n)); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript program to find // element that appears once // function which find number function singleNumber(nums,n) { let m = new Map(); let sum1 = 0, sum2 = 0; for (let i = 0; i < n; i++) { if (!m.has(nums[i])) { sum1 += nums[i]; m.set(nums[i], 1); } sum2 += nums[i]; } // applying the formula. return (2 * (sum1) - sum2); } // Driver code let a=[2, 3, 5, 4, 5, 3, 4]; let n = 7; document.write(singleNumber(a,n)+ "<br>" ); let b=[15, 18, 16, 18, 16, 15, 89]; document.write(singleNumber(b,n)); // This code is contributed by unknown2108 </script> |
输出：
289
另一种方法：
这是在重复元素列表中查找单个元素的有效方法。在这种方法中，我们使用二进制搜索算法来查找重复元素列表中的单个元素。在此之前，我们需要确保数组是否已排序。第一步是对数组进行排序，因为如果数组未排序，二进制搜索算法将无法工作。
现在让我们转到二进制搜索实现：
数组中只有一个元素创建了两个半元素，即左半元素和右半元素。如果左半部分中存在重复项，那么左半部分中重复元素的第一个实例是偶数索引，第二个实例是奇数索引。左半部分的相反部分发生在右半部分（第一个实例是奇数索引，第二个实例是偶数索引）。现在应用二进制搜索算法：
1） 解决方案是获取数组的两个索引（低和高），其中 低的 指向数组索引0和 高的 指向数组索引（数组大小为2）。我们从（低+高）/2的值中取出中间指数。
2） 现在检查中间索引值是落在左半部分还是落在右半部分。如果它落在左半部分，那么我们将低值改为中+1，如果它落在右半部分，那么我们将高指数改为中-1。为了检验它，我们使用了一种逻辑( 如果（arr[mid]==arr[mid^1] )如果mid是偶数，那么mid^1将是下一个奇数索引，如果条件得到满足，那么我们可以说我们在左索引中，否则我们可以说我们在右半索引中。但是如果mid是一个奇数指数，那么mid^1会把我们带到mid-1，这是之前的偶数指数，它等于意味着我们在右半部分，否则在左半部分。
3） 之所以这样做，是因为此实现的目标是在重复列表中找到单个元素。只有当low value大于high value时才有可能，因为此时low将指向包含数组中单个元素的索引。
4） 循环结束后，我们返回低索引的值。
C++
#include <bits/stdc++.h> using namespace std; int singleelement( int arr[], int n) { int low = 0, high = n - 2; int mid; while (low <= high) { mid = (low + high) / 2; if (arr[mid] == arr[mid ^ 1]) { low = mid + 1; } else { high = mid - 1; } } return arr[low]; } int main() { int arr[] = { 2, 3, 5, 4, 5, 3, 4 }; int size = sizeof (arr) / sizeof (arr[0]); sort(arr, arr + size); cout << singleelement(arr, size); return 0; } // This code is contributed by Sohom Das |
JAVA
import java.io.*; import java.util.Arrays; class GFG{ static int singleelement( int arr[], int n) { int low = 0 , high = n - 2 ; int mid; while (low <= high) { mid = (low + high) / 2 ; if (arr[mid] == arr[mid ^ 1 ]) { low = mid + 1 ; } else { high = mid - 1 ; } } return arr[low]; } // Driver code public static void main(String[] args) { int arr[] = { 2 , 3 , 5 , 4 , 5 , 3 , 4 }; int size = 7 ; Arrays.sort(arr); System.out.println(singleelement(arr, size)); } } // This code is contributed by dassohom5 |
Python3
def singleelement(arr, n): low = 0 high = n - 2 mid = 0 while (low < = high): mid = (low + high) / / 2 if (arr[mid] = = arr[mid ^ 1 ]): low = mid + 1 else : high = mid - 1 return arr[low] # Driver code arr = [ 2 , 3 , 5 , 4 , 5 , 3 , 4 ] size = len (arr) arr.sort() print (singleelement(arr, size)) # This code is contributed by shivanisingh |
C#
using System; using System.Collections; class GFG{ static int singleelement( int [] arr, int n) { int low = 0, high = n - 2; int mid; while (low <= high) { mid = (low + high) / 2; if (arr[mid] == arr[mid ^ 1]) { low = mid + 1; } else { high = mid - 1; } } return arr[low]; } // Driver code public static void Main() { int [] arr = { 2, 3, 5, 4, 5, 3, 4 }; int size = 7; Array.Sort(arr); Console.WriteLine(singleelement(arr, size)); } } // This code is contributed by dassohom5 |
Javascript
<script> function singleelement(arr,n) { let low = 0, high = n - 2; let mid; while (low <= high) { mid = (low + high) / 2; if (arr[mid] == arr[mid ^ 1]) { low = mid + 1; } else { high = mid - 1; } } return arr[low]; } let arr = [ 2, 3, 5, 4, 5, 3, 4 ]; let size = arr.length; document.write(singleelement(arr, size)); </script> |
输出：
2
解的时间复杂度为O（nlog（N））+O（logn），空间复杂度为O（1）。
本文由 拉维 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
