SG要求 给定一个数组，其中除两个以外的所有数字都重复一次。（即，我们有2n+2个数字，n个数字出现两次，其余两个出现一次）。以最有效的方式找到这两个数字。
null
方法1（使用排序） 首先，对所有元素进行排序。在排序数组中，通过比较相邻元素，我们可以很容易地得到非重复元素。该方法的时间复杂度为O（nLogn）
方法2（使用XOR） 设x和y为我们正在寻找的非重复元素，arr[]为输入数组。首先，计算所有数组元素的异或。
xor = arr[0]^arr[1]^arr[2].....arr[n-1]
在异或中设置的所有位将设置在一个非重复元素（x或y）中，而不是其他元素中。所以，如果我们取xor的任意一个集合位，将数组中的元素分成两个集合——一个集合中的元素具有相同的位集合，另一个集合中的元素具有相同的未设置位集合。通过这样做，我们将在一组中得到x，在另一组中得到y。现在，如果我们对第一个集合中的所有元素进行异或运算，我们将得到第一个非重复元素，通过在其他集合中进行同样的运算，我们将得到第二个非重复元素。
Let us see an example. arr[] = {2, 4, 7, 9, 2, 4}1) Get the XOR of all the elements. xor = 2^4^7^9^2^4 = 14 (1110)2) Get a number which has only one set bit of the xor. Since we can easily get the rightmost set bit, let us use it. set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010 Now set_bit_no will have only set as rightmost set bit of xor.3) Now divide the elements in two sets and do xor of elements in each set and we get the non-repeating elements 7 and 9. Please see the implementation for this step.
方法： 第一步： 将数组的所有元素Xor成一个变量和，因此数组中出现两次的所有元素都将被删除，例如，4=“100”，如果4 Xor 4=>“100”Xor“100”，那么答案将是“000”。 第二步： 因此，在求和中，最终答案将是3或5，因为2和4都是异或，其本身为0，因此sum=“011”xor“101”即sum=“110”=6。 第三步： 现在我们将取2的和的补码，即（-sum）=“010”。 第4步： 现在，按位和2的总和，即“110”和“010”给出了答案“010”（按位的目标是，我们想要得到一个只包含最右边的集合位的数字）。 第5步： 按位&数组的所有元素与此获得的和，2=“010”和“010”=2，3=“011”和“010”=010，4=“100”和“010”=000，5=“101”和“010”=000。 第6步： 正如我们所看到的，2,3的按位与大于0，因此它们将与sum1异或，4,5的按位与等于0，因此它们将与sum2异或。 第7步： 因为2存在两次，所以用sum1获取异或两次，结果3存储在其中，而因为4也存在两次，所以用sum2获取异或将取消它的值，因此只有5将保留在那里。
实施：
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; /* This function sets the values of *x and *y to non-repeating elements in an array arr[] of size n*/ void get2NonRepeatingNos( int arr[], int n, int * x, int * y) { /* Will hold Xor of all elements */ int Xor = arr[0]; /* Will have only single set bit of Xor */ int set_bit_no; int i; *x = 0; *y = 0; /* Get the Xor of all elements */ for (i = 1; i < n; i++) Xor ^= arr[i]; /* Get the rightmost set bit in set_bit_no */ set_bit_no = Xor & ~(Xor - 1); /* Now divide elements in two sets by comparing rightmost set bit of Xor with bit at same position in each element. */ for (i = 0; i < n; i++) { /*Xor of first set */ if (arr[i] & set_bit_no) *x = *x ^ arr[i]; /*Xor of second set*/ else { *y = *y ^ arr[i]; } } } /* Driver code */ int main() { int arr[] = { 2, 3, 7, 9, 11, 2, 3, 11 }; int n = sizeof (arr) / sizeof (*arr); int * x = new int [( sizeof ( int ))]; int * y = new int [( sizeof ( int ))]; get2NonRepeatingNos(arr, n, x, y); cout << "The non-repeating elements are " << *x << " and " << *y; } // This code is contributed by rathbhupendra |
C
// C program for above approach #include <stdio.h> #include <stdlib.h> /* This function sets the values of *x and *y to non-repeating elements in an array arr[] of size n*/ void get2NonRepeatingNos( int arr[], int n, int * x, int * y) { /* Will hold Xor of all elements */ int Xor = arr[0]; /* Will have only single set bit of Xor */ int set_bit_no; int i; *x = 0; *y = 0; /* Get the Xor of all elements */ for (i = 1; i < n; i++) Xor ^= arr[i]; /* Get the rightmost set bit in set_bit_no */ set_bit_no = Xor & ~(Xor - 1); /* Now divide elements in two sets by comparing rightmost set bit of Xor with bit at same position in each element. */ for (i = 0; i < n; i++) { /*Xor of first set */ if (arr[i] & set_bit_no) *x = *x ^ arr[i]; /*Xor of second set*/ else { *y = *y ^ arr[i]; } } } /* Driver program to test above function */ int main() { int arr[] = { 2, 3, 7, 9, 11, 2, 3, 11 }; int * x = ( int *) malloc ( sizeof ( int )); int * y = ( int *) malloc ( sizeof ( int )); get2NonRepeatingNos(arr, 8, x, y); printf ( "The non-repeating elements are %d and %d" , *x, *y); getchar (); } |
JAVA
// Java Program for above approach public class UniqueNumbers { // This function sets the values of // *x and *y to non-repeating elements // in an array arr[] of size n public static void UniqueNumbers2( int [] arr, int n) { int sum = 0 ; for ( int i = 0 ; i < n; i++) { // Xor all the elements of the array // all the elements occurring twice will // cancel out each other remaining // two unique numbers will be xored sum = (sum ^ arr[i]); } // Bitwise & the sum with it's 2's Complement // Bitwise & will give us the sum containing // only the rightmost set bit sum = (sum & -sum); // sum1 and sum2 will contains 2 unique // elements initialized with 0 box // number xored with 0 is number itself int sum1 = 0 ; int sum2 = 0 ; // traversing the array again for ( int i = 0 ; i < arr.length; i++) { // Bitwise & the arr[i] with the sum // Two possibilities either result == 0 // or result > 0 if ((arr[i] & sum) > 0 ) { // if result > 0 then arr[i] xored // with the sum1 sum1 = (sum1 ^ arr[i]); } else { // if result == 0 then arr[i] // xored with sum2 sum2 = (sum2 ^ arr[i]); } } // print the the two unique numbers System.out.println( "The non-repeating elements are " + sum1 + " and " + sum2); } public static void main(String[] args) { int [] arr = new int [] { 2 , 3 , 7 , 9 , 11 , 2 , 3 , 11 }; int n = arr.length; UniqueNumbers2(arr, n); } } // This code is contributed by Parshav Nahta |
蟒蛇3
# Python3 program for above approach # This function sets the values of # *x and *y to non-repeating elements # in an array arr[] of size n def UniqueNumbers2(arr, n): sums = 0 for i in range ( 0 , n): # Xor all the elements of the array # all the elements occurring twice will # cancel out each other remaining # two unique numbers will be xored sums = (sums ^ arr[i]) # Bitwise & the sum with it's 2's Complement # Bitwise & will give us the sum containing # only the rightmost set bit sums = (sums & - sums) # sum1 and sum2 will contains 2 unique # elements initialized with 0 box # number xored with 0 is number itself sum1 = 0 sum2 = 0 # Traversing the array again for i in range ( 0 , len (arr)): # Bitwise & the arr[i] with the sum # Two possibilities either result == 0 # or result > 0 if (arr[i] & sums) > 0 : # If result > 0 then arr[i] xored # with the sum1 sum1 = (sum1 ^ arr[i]) else : # If result == 0 then arr[i] # xored with sum2 sum2 = (sum2 ^ arr[i]) # Print the the two unique numbers print ( "The non-repeating elements are " , sum1, " and " , sum2) # Driver Code if __name__ = = "__main__" : arr = [ 2 , 3 , 7 , 9 , 11 , 2 , 3 , 11 ] n = len (arr) UniqueNumbers2(arr, n) # This code is contributed by akhilsaini |
C#
// C# program for above approach using System; class GFG { // This function sets the values of // *x and *y to non-repeating elements // in an array arr[] of size n static void UniqueNumbers2( int [] arr, int n) { int sum = 0; for ( int i = 0; i < n; i++) { // Xor all the elements of the array // all the elements occurring twice will // cancel out each other remaining // two unique numbers will be xored sum = (sum ^ arr[i]); } // Bitwise & the sum with it's 2's Complement // Bitwise & will give us the sum containing // only the rightmost set bit sum = (sum & -sum); // sum1 and sum2 will contains 2 unique // elements initialized with 0 box // number xored with 0 is number itself int sum1 = 0; int sum2 = 0; // Traversing the array again for ( int i = 0; i < arr.Length; i++) { // Bitwise & the arr[i] with the sum // Two possibilities either result == 0 // or result > 0 if ((arr[i] & sum) > 0) { // If result > 0 then arr[i] xored // with the sum1 sum1 = (sum1 ^ arr[i]); } else { // If result == 0 then arr[i] // xored with sum2 sum2 = (sum2 ^ arr[i]); } } // Print the the two unique numbers Console.WriteLine( "The non-repeating " + "elements are " + sum1 + " and " + sum2); } // Driver Code static public void Main() { int [] arr = { 2, 3, 7, 9, 11, 2, 3, 11 }; int n = arr.Length; UniqueNumbers2(arr, n); } } // This code is contributed by akhilsaini |
Javascript
<script> // Javascript program for above approach // This function sets the values of // *x and *y to non-repeating elements // in an array arr[] of size n function UniqueNumbers2(arr, n) { let sum = 0; for (let i = 0; i < n; i++) { // Xor all the elements of the array // all the elements occurring twice will // cancel out each other remaining // two unique numbers will be xored sum = (sum ^ arr[i]); } // Bitwise & the sum with it's 2's Complement // Bitwise & will give us the sum containing // only the rightmost set bit sum = (sum & -sum); // sum1 and sum2 will contains 2 unique // elements initialized with 0 box // number xored with 0 is number itself let sum1 = 0; let sum2 = 0; // Traversing the array again for (let i = 0; i < arr.length; i++) { // Bitwise & the arr[i] with the sum // Two possibilities either result == 0 // or result > 0 if ((arr[i] & sum) > 0) { // If result > 0 then arr[i] xored // with the sum1 sum1 = (sum1 ^ arr[i]); } else { // If result == 0 then arr[i] // xored with sum2 sum2 = (sum2 ^ arr[i]); } } // Print the the two unique numbers document.write( "The non-repeating " + "elements are " + sum1 + " and " + sum2); } let arr = [ 2, 3, 7, 9, 11, 2, 3, 11 ]; let n = arr.length; UniqueNumbers2(arr, n); // This code is contributed by vaibhavrabadiya117. </script> |
输出
The non-repeating elements are 7 and 9
时间复杂性： O（n） 辅助空间： O（1）
详细解释请参考以下帖子： 在未排序的数组中查找出现奇数的两个数字
方法3（使用地图）
在这种方法中，我们只需计算每个元素的频率。频率等于1的元素是不重复的数字。下面的代码解释了解决方案-
C++
// C++ program for Find the two non-repeating elements in // an array of repeating elements/ Unique Numbers 2 #include <bits/stdc++.h> using namespace std; /* This function prints the two non-repeating elements in an * array of repeating elements*/ void get2NonRepeatingNos( int arr[], int n) { /*Create map and calculate frequency of array elements.*/ map< int , int > m; for ( int i = 0; i < n; i++) { m[arr[i]]++; } /*Traverse through the map and check if its second element that is the frequency is 1 or not. If this is 1 than it is the non-repeating element print it.It is clearly mentioned in problem that all numbers except two are repeated once. So they will be printed*/ cout << "The non-repeating elements are " ; for ( auto & x : m) { if (x.second == 1) { cout << x.first << " " ; } } } /* Driver code */ int main() { int arr[] = { 2, 3, 7, 9, 11, 2, 3, 11 }; int n = sizeof (arr) / sizeof (arr[0]); get2NonRepeatingNos(arr, n); } // This code is contributed by Abhishek |
JAVA
/*package whatever //do not write package name here */ //Java program to find 2 non repeating elements //in array that has pairs of numbers import java.util.*; import java.io.*; class GFG { //Method to print the 2 non repeating elements in an array public static void print2SingleNumbers( int [] nums){ /*We use a TreeMap to store the elements in the sorted order*/ TreeMap<Integer, Integer> map = new TreeMap<>(); int n = nums.length; /*Iterate through the array and check if each element is present or not in the map. If the element is present, remove it from the array otherwise add it to the map*/ for ( int i = 0 ; i<n; i++){ if (map.containsKey(nums[i])) map.remove(nums[i]); else map.put(nums[i], 1 ); } System.out.println( "The non-repeating integers are " + map.firstKey() + " " + map.lastKey()); } //Driver code public static void main (String[] args) { int [] nums = new int []{ 2 , 11 , 3 , 11 , 7 , 3 , 9 , 2 }; print2SingleNumbers(nums); } //This code is contributed by Satya Anvesh R } |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; public class GFG { // Method to print the 2 non repeating elements in an array public static void print2SingleNumbers( int [] A) { /*We use a TreeMap to store the elements in the sorted order*/ Dictionary< int , int > map = new Dictionary< int , int >(); int n = A.Length; /*Iterate through the array and check if each element is present or not in the map. If the element is present, remove it from the array otherwise add it to the map*/ for ( int i = 0 ; i < n; i++) { if (map.ContainsKey(A[i])) map.Remove(A[i]); else map.Add(A[i], 1); } Console.Write( "The non-repeating integers are " ); foreach (KeyValuePair< int , int > it in map){ if (it.Value == 1) { Console.Write(it.Key + " " ); } } } // Driver Code public static void Main(String[] args) { int [] nums = new int []{2, 11, 3, 11, 7, 3, 9, 2}; print2SingleNumbers(nums); } } // This code is contributed by code_hunt. |
Javascript
<script> // JavaScript program for Find the two non-repeating elements in // an array of repeating elements/ Unique Numbers 2 /* This function prints the two non-repeating elements in an * array of repeating elements*/ function get2NonRepeatingNos(arr, n) { /*Create map and calculate frequency of array elements.*/ let m = new Map(); for (let i = 0; i < n; i++) { if (!m.has(arr[i])) { m.set(arr[i],0); } m.set(arr[i],m.get(arr[i])+1); } /*Traverse through the map and check if its second element that is the frequency is 1 or not. If this is 1 than it is the non-repeating element print it.It is clearly mentioned in problem that all numbers except two are repeated once. So they will be printed*/ document.write( "The non-repeating elements are " ); for (let [key,value] of m) { if (value == 1) { document.write(key, " " ); } } } /* Driver code */ let arr = [ 2, 3, 7, 9, 11, 2, 3, 11 ]; let n = arr.length; get2NonRepeatingNos(arr, n); // This code is contributed by shinjanpatra </script> |
输出
The non-repeating elements are 7 9
时间复杂性 ：O（nlogn） 辅助空间 ：O（n）
方法4（使用集合）：
在这个方法中，我们检查元素是否已经存在，如果它存在，我们移除它，否则我们将它添加到集合中。
方法 :
第一步 ：取每个元素，检查其是否存在于集合中。如果存在，请转至步骤3。如果不存在，请转至步骤2。
第二步 ：将元素添加到集合中并转至步骤4。
第三步 ：从集合中移除元素并转至步骤4。
第四步 ：打印集合的元素。
实施：
JAVA
/*package whatever //do not write package name here */ //Java program to find 2 non repeating elements //in array that has pairs of numbers import java.util.LinkedHashSet; import java.util.Iterator; import java.io.*; class GFG { //Method to print the 2 non repeating elements in an array public static void print2SingleNumbers( int [] nums){ // Create a Map Set to store the numbers LinkedHashSet<Integer> set = new LinkedHashSet<>(); int n = nums.length; /*Iterate through the array and check if each element is present or not in the set. If the element is present, remove it from the array otherwise add it to the set*/ for ( int i = 0 ; i<n; i++){ if (set.contains(nums[i])) set.remove(nums[i]); else set.add(nums[i]); } //Iterator is used to traverse through the set Iterator<Integer> i = set.iterator(); /*Since there will only be 2 non-repeating elements we can directly print them*/ System.out.println( "The 2 non repeating numbers are : " + i.next() + " " + i.next()); } //Driver code public static void main (String[] args) { int [] nums = new int []{ 2 , 3 , 7 , 9 , 11 , 2 , 3 , 11 }; print2SingleNumbers(nums); } //This code contributed by Satya Anvesh R } |
输出
The 2 non repeating numbers are : 7 9
C++
// C++ program for Find the two non-repeating elements in // an array of repeating elements/ Unique Numbers 2 #include <bits/stdc++.h> using namespace std; /* This function prints the two non-repeating elements in an * array of repeating elements*/ void get2NonRepeatingNos( int arr[], int n) { /*Create map and calculate frequency of array elements.*/ // Create a Map Set to store the numbers set< int > s; for ( int i = 0; i < n; i++) { /*Iterate through the array and check if each element is present or not in the set. If the element is present, remove it from the array otherwise add it to the set*/ if (s.find(arr[i]) != s.end()) s.erase(arr[i]); else s.insert(arr[i]); } cout << "The 2 non repeating numbers are : " ; for ( auto it : s) cout << it << " " ; cout << endl; } /* Driver code */ int main() { int arr[] = {2, 3, 7, 9, 11, 2, 3, 11}; int n = sizeof (arr) / sizeof (arr[0]); get2NonRepeatingNos(arr, n); } // This code is contributed by Aditya kumar |
Javascript
<script> // JavaScript program for Find the two non-repeating elements in // an array of repeating elements/ Unique Numbers 2 /* This function prints the two non-repeating elements in an * array of repeating elements*/ function get2NonRepeatingNos(arr, n) { // Create a Set to store the numbers let s = new Set(); for (let i = 0; i < n; i++) { /*Iterate through the array and check if each element is present or not in the set. If the element is present, remove it from the array otherwise add it to the set*/ if (s.has(arr[i])) s. delete (arr[i]); else s.add(arr[i]); } document.write( "The 2 non repeating numbers are : " ); for (const it of s) document.write(it, " " ); document.write( "</br>" ); } /* Driver code */ let arr = [2, 3, 7, 9, 11, 2, 3, 11]; let n = arr.length; get2NonRepeatingNos(arr, n); // This code is contributed by shinjanpatra </script> |
输出
The 2 non repeating numbers are : 7 9
时间复杂度：O（nlogn）
辅助空间：O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
