你会得到一个由n+2个元素组成的数组。数组的所有元素都在1到n的范围内。除了两个数字出现两次之外，所有元素都出现一次。找出两个重复的数字。
null
例子：
输入： arr=[4,2,4,5,2,3,1] n=5 输出： 4 2 说明： 上述数组有n+2=7个元素，除2和4出现两次外，所有元素都出现一次。所以输出应该是42。
方法1（基础）
使用两个循环。在外部循环中，逐个拾取元素，并计算所拾取元素在内部循环中的出现次数。 该方法不使用问题中提供的其他有用数据，例如数字范围在1到n之间，并且只有两个重复元素。
C++
// C++ program to Find the two repeating // elements in a given array #include<bits/stdc++.h> using namespace std; void printRepeating( int arr[], int size) { int i, j; printf ( " Repeating elements are " ); for (i = 0; i < size-1; i++) for (j = i + 1; j < size; j++) if (arr[i] == arr[j]) cout << arr[i] << " " ; } // Driver Code int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); } // This code is contributed by Shivi_Aggarwal |
C
#include<stdio.h> #include<stdlib.h> void printRepeating( int arr[], int size) { int i, j; printf ( " Repeating elements are " ); for (i = 0; i < size-1; i++) for (j = i+1; j < size; j++) if (arr[i] == arr[j]) printf ( " %d " , arr[i]); } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); getchar (); return 0; } |
JAVA
class RepeatElement { void printRepeating( int arr[], int size) { int i, j; System.out.println( "Repeated Elements are :" ); for (i = 0 ; i < size- 1 ; i++) { for (j = i + 1 ; j < size; j++) { if (arr[i] == arr[j]) System.out.print(arr[i] + " " ); } } } public static void main(String[] args) { RepeatElement repeat = new RepeatElement(); int arr[] = { 4 , 2 , 4 , 5 , 2 , 3 , 1 }; int arr_size = arr.length; repeat.printRepeating(arr, arr_size); } } |
Python3
# Python3 program to Find the two # repeating elements in a given array def printRepeating(arr, size): print ( "Repeating elements are " , end = '') for i in range ( 0 , size - 1 ): for j in range (i + 1 , size): if arr[i] = = arr[j]: print (arr[i], end = ' ' ) # Driver code arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 1 ] arr_size = len (arr) printRepeating(arr, arr_size) # This code is contributed by Smitha Dinesh Semwal |
C#
using System; class GFG { static void printRepeating( int []arr, int size) { int i, j; Console.Write( "Repeated Elements are :" ); for (i = 0; i < size-1; i++) { for (j = i + 1; j < size; j++) { if (arr[i] == arr[j]) Console.Write(arr[i] + " " ); } } } // driver code public static void Main() { int []arr = {4, 2, 4, 5, 2, 3, 1}; int arr_size = arr.Length; printRepeating(arr, arr_size); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to Find the two // repeating elements in // a given array function printRepeating( $arr , $size ) { $i ; $j ; echo " Repeating elements are " ; for ( $i = 0; $i < $size -1; $i ++) for ( $j = $i + 1; $j < $size ; $j ++) if ( $arr [ $i ] == $arr [ $j ]) echo $arr [ $i ], " " ; } // Driver Code $arr = array (4, 2, 4, 5, 2, 3, 1); $arr_size = sizeof( $arr , 0); printRepeating( $arr , $arr_size ); // This code is contributed by Ajit ?> |
Javascript
<script> function printRepeating(arr , size) { var i, j; document.write( "Repeated Elements are :" ); for (i = 0; i < size-1; i++) { for (j = i + 1; j < size; j++) { if (arr[i] == arr[j]) document.write(arr[i] + " " ); } } } var arr = [4, 2, 4, 5, 2, 3, 1]; var arr_size = arr.length; printRepeating(arr, arr_size); // This code is contributed by 29AjayKumar </script> |
输出
Repeating elements are 4 2
时间复杂性： O（n*n） 辅助空间： O（1）
方法2（使用计数数组） 遍历数组一次。在遍历时，使用大小为n的临时数组count[]跟踪数组中所有元素的计数，当看到已设置计数的元素时，将其打印为副本。 此方法使用问题中给出的范围来限制计数[]的大小，但不使用只有两个重复元素的数据。
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; void printRepeating( int arr[], int size) { int *count = new int [ sizeof ( int )*(size - 2)]; int i; cout << " Repeating elements are " ; for (i = 0; i < size; i++) { if (count[arr[i]] == 1) cout << arr[i] << " " ; else count[arr[i]]++; } } // Driver code int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); return 0; } // This is code is contributed by rathbhupendra |
C
#include<stdio.h> #include<stdlib.h> void printRepeating( int arr[], int size) { int *count = ( int *) calloc ( sizeof ( int ), (size - 2)); int i; printf ( " Repeating elements are " ); for (i = 0; i < size; i++) { if (count[arr[i]] == 1) printf ( " %d " , arr[i]); else count[arr[i]]++; } } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); getchar (); return 0; } |
JAVA
class RepeatElement { void printRepeating( int arr[], int size) { int count[] = new int [size]; int i; System.out.println( "Repeated elements are : " ); for (i = 0 ; i < size; i++) { if (count[arr[i]] == 1 ) System.out.print(arr[i] + " " ); else count[arr[i]]++; } } public static void main(String[] args) { RepeatElement repeat = new RepeatElement(); int arr[] = { 4 , 2 , 4 , 5 , 2 , 3 , 1 }; int arr_size = arr.length; repeat.printRepeating(arr, arr_size); } } |
Python3
# Python3 code for Find the two repeating # elements in a given array def printRepeating(arr,size) : count = [ 0 ] * size print ( " Repeating elements are " ,end = "") for i in range ( 0 , size) : if (count[arr[i]] = = 1 ) : print (arr[i], end = " " ) else : count[arr[i]] = count[arr[i]] + 1 # Driver code arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 1 ] arr_size = len (arr) printRepeating(arr, arr_size) # This code is contributed by Nikita Tiwari. |
C#
// C# program to Find the two // repeating elements in a given array using System; class GFG { static void printRepeating( int []arr, int size) { int []count = new int [size]; int i; Console.Write( "Repeated elements are: " ); for (i = 0; i < size; i++) { if (count[arr[i]] == 1) Console.Write(arr[i] + " " ); else count[arr[i]]++; } } // driver code public static void Main() { int []arr = {4, 2, 4, 5, 2, 3, 1}; int arr_size = arr.Length; printRepeating(arr, arr_size); } } //This code is contributed by Sam007 |
PHP
<?php // PHP program to Find the two // repeating elements in a given array function printRepeating( $arr , $size ) { $count = array_fill (0, $size , 0); echo "Repeated elements are " ; for ( $i = 0; $i < $size ; $i ++) { if ( $count [ $arr [ $i ]] == 1) echo $arr [ $i ]. " " ; else $count [ $arr [ $i ]]++; } } // Driver code $arr = array (4, 2, 4, 5, 2, 3, 1); $arr_size = count ( $arr ); printRepeating( $arr , $arr_size ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to Find the two // repeating elements in a given array function printRepeating(arr, size) { let count = new Array(size); count.fill(0); let i; document.write( "Repeating elements are " ); for (i = 0; i < size; i++) { if (count[arr[i]] == 1) document.write(arr[i] + " " ); else count[arr[i]]++; } } let arr = [4, 2, 4, 5, 2, 3, 1]; let arr_size = arr.length; printRepeating(arr, arr_size); </script> |
输出
Repeating elements are 4 2
时间复杂性： O（n） 辅助空间： O（n）
方法3（制作两个方程式）
让重复的数字是X和Y。我们为X和Y建立两个方程，剩下的简单任务是求解这两个方程。 我们知道从1到n的整数之和是n（n+1）/2，乘积是n！。我们计算输入数组的和，当这个和从n（n+1）/2中减去时，我们得到X+Y，因为X和Y是集合[1..n]中缺少的两个数字。同样地，计算输入数组的乘积，当该乘积除以n！，我们得到X*Y。给定X和Y的和和和积，我们可以很容易地找到X和Y。 让数组中所有数字的总和为S，乘积为P X+Y=S–n（n+1）/2 XY=P/n！ 利用以上两个方程，我们可以求出X和Y。对于array=4 2 5 2 3 1，我们得到S=21，P为960。 X+Y=21–15=6 XY=960/5！=8. X-Y=sqrt（（X+Y）^2-4*XY）=sqrt（4）=2 使用下面两个方程，我们很容易得到X=（6+2）/2和Y=（6-2）/2 X+Y=6 X–Y=2 感谢geek4u推荐这种方法。正如初学者所指出的，这种方法可能存在加法和乘法溢出问题。
方法3和4使用问题中给出的所有有用信息：
C++
#include <bits/stdc++.h> using namespace std; /* function to get factorial of n */ int fact( int n); void printRepeating( int arr[], int size) { int S = 0; /* S is for sum of elements in arr[] */ int P = 1; /* P is for product of elements in arr[] */ int x, y; /* x and y are two repeating elements */ int D; /* D is for difference of x and y, i.e., x-y*/ int n = size - 2, i; /* Calculate Sum and Product of all elements in arr[] */ for (i = 0; i < size; i++) { S = S + arr[i]; P = P*arr[i]; } S = S - n*(n+1)/2; /* S is x + y now */ P = P/fact(n); /* P is x*y now */ D = sqrt (S*S - 4*P); /* D is x - y now */ x = (D + S)/2; y = (S - D)/2; cout<< "The two Repeating elements are " <<x<< " & " <<y; } int fact( int n) { return (n == 0)? 1 : n*fact(n-1); } // Driver code int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); return 0; } // This code is contributed by rathbhupendra |
C
#include<stdio.h> #include<stdlib.h> #include<math.h> /* function to get factorial of n */ int fact( int n); void printRepeating( int arr[], int size) { int S = 0; /* S is for sum of elements in arr[] */ int P = 1; /* P is for product of elements in arr[] */ int x, y; /* x and y are two repeating elements */ int D; /* D is for difference of x and y, i.e., x-y*/ int n = size - 2, i; /* Calculate Sum and Product of all elements in arr[] */ for (i = 0; i < size; i++) { S = S + arr[i]; P = P*arr[i]; } S = S - n*(n+1)/2; /* S is x + y now */ P = P/fact(n); /* P is x*y now */ D = sqrt (S*S - 4*P); /* D is x - y now */ x = (D + S)/2; y = (S - D)/2; printf ( "The two Repeating elements are %d & %d" , x, y); } int fact( int n) { return (n == 0)? 1 : n*fact(n-1); } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); getchar (); return 0; } |
JAVA
class RepeatElement { void printRepeating( int arr[], int size) { /* S is for sum of elements in arr[] */ int S = 0 ; /* P is for product of elements in arr[] */ int P = 1 ; /* x and y are two repeating elements */ int x, y; /* D is for difference of x and y, i.e., x-y*/ int D; int n = size - 2 , i; /* Calculate Sum and Product of all elements in arr[] */ for (i = 0 ; i < size; i++) { S = S + arr[i]; P = P * arr[i]; } /* S is x + y now */ S = S - n * (n + 1 ) / 2 ; /* P is x*y now */ P = P / fact(n); /* D is x - y now */ D = ( int ) Math.sqrt(S * S - 4 * P); x = (D + S) / 2 ; y = (S - D) / 2 ; System.out.println( "The two repeating elements are :" ); System.out.print(x + " " + y); } int fact( int n) { return (n == 0 ) ? 1 : n * fact(n - 1 ); } public static void main(String[] args) { RepeatElement repeat = new RepeatElement(); int arr[] = { 4 , 2 , 4 , 5 , 2 , 3 , 1 }; int arr_size = arr.length; repeat.printRepeating(arr, arr_size); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python3 code for Find the two repeating # elements in a given array import math def printRepeating(arr, size) : # S is for sum of elements in arr[] S = 0 ; # P is for product of elements in arr[] P = 1 ; n = size - 2 # Calculate Sum and Product # of all elements in arr[] for i in range ( 0 , size) : S = S + arr[i] P = P * arr[i] # S is x + y now S = S - n * (n + 1 ) / / 2 # P is x*y now P = P / / fact(n) # D is x - y now D = math.sqrt(S * S - 4 * P) x = (D + S) / / 2 y = (S - D) / / 2 print ( "The two Repeating elements are " , ( int )(x), " & " ,( int )(y)) def fact(n) : if (n = = 0 ) : return 1 else : return (n * fact(n - 1 )) # Driver code arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 1 ] arr_size = len (arr) printRepeating(arr, arr_size) # This code is contributed by Nikita Tiwari. |
C#
using System; class GFG { static void printRepeating( int []arr, int size) { /* S is for sum of elements in arr[] */ int S = 0; /* P is for product of elements in arr[] */ int P = 1; /* x and y are two repeating elements */ int x, y; /* D is for difference of x and y, i.e., x-y*/ int D; int n = size - 2, i; /* Calculate Sum and Product of all elements in arr[] */ for (i = 0; i < size; i++) { S = S + arr[i]; P = P * arr[i]; } /* S is x + y now */ S = S - n * (n + 1) / 2; /* P is x*y now */ P = P / fact(n); /* D is x - y now */ D = ( int ) Math.Sqrt(S * S - 4 * P); x = (D + S) / 2; y = (S - D) / 2; Console.WriteLine( "The two" + " repeating elements are :" ); Console.Write(x + " " + y); } static int fact( int n) { return (n == 0) ? 1 : n * fact(n - 1); } // driver code public static void Main() { int []arr = {4, 2, 4, 5, 2, 3, 1}; int arr_size = arr.Length; printRepeating(arr, arr_size); } } // This code is contributed by Sam007 |
PHP
<?php /* function to get factorial of n */ function fact( $n ){ return ( $n == 0)? 1 : $n *fact( $n -1); } function printRepeating( $arr , $size ) { $S = 0; /* S is for sum of elements in arr[] */ $P = 1; /* P is for product of elements in arr[] */ $x ; $y ; /* x and y are two repeating elements */ $D ; /* D is for difference of x and y, i.e., x-y*/ $n = $size - 2; /* Calculate Sum and Product of all elements in arr[] */ for ( $i = 0; $i < $size ; $i ++) { $S = $S + $arr [ $i ]; $P = $P * $arr [ $i ]; } $S = $S - $n *( $n +1)/2; /* S is x + y now */ $P = $P /fact( $n ); /* P is x*y now */ $D = sqrt( $S * $S - 4* $P ); /* D is x - y now */ $x = ( $D + $S )/2; $y = ( $S - $D )/2; echo "The two Repeating elements are " . $x . " & " . $y ; } $arr = array (4, 2, 4, 5, 2, 3, 1); $arr_size = count ( $arr ); printRepeating( $arr , $arr_size ); ?> |
Javascript
<script> function printRepeating(arr , size) { /* S is for sum of elements in arr */ var S = 0; /* P is for product of elements in arr */ var P = 1; /* x and y are two repeating elements */ var x, y; /* D is for difference of x and y, i.e., x-y*/ var D; var n = size - 2, i; /* Calculate Sum and Product of all elements in arr */ for (i = 0; i < size; i++) { S = S + arr[i]; P = P * arr[i]; } /* S is x + y now */ S = S - n * parseInt((n + 1) / 2); /* P is x*y now */ P = parseInt(P / fact(n)); /* D is x - y now */ D = parseInt( Math.sqrt(S * S - 4 * P)); x = parseInt((D + S) / 2); y = parseInt((S - D) / 2); document.write( "The two repeating elements are : " ); document.write(x + " & " + y); } function fact(n) { var ans = false ; if (n == 0) return 1; else return (n * fact(n - 1)); } var arr = [4, 2, 4, 5, 2, 3, 1]; var arr_size = arr.length; printRepeating(arr, arr_size); // This code is contributed by 29AjayKumar </script> |
输出
The two Repeating elements are 4 & 2
时间复杂性： O（n） 辅助空间： O（1）
方法4（使用XOR）
感谢新手推荐这种方法。 这里使用的方法类似于本文的方法2 这篇帖子 . 设重复数为X和Y，如果我们对数组中的所有元素和从1到n的所有整数进行异或运算，那么结果就是X或Y。 X xor Y的二进制表示中的1对应于X和Y之间的不同位。假设X xor Y的第k位为1，我们可以对数组中的所有元素和从1到n的所有整数进行异或运算，其中第k位为1。结果将是X和Y中的一个。
C++
#include <bits/stdc++.h> using namespace std; void printRepeating( int arr[], int size) { int Xor = arr[0]; /* Will hold Xor of all elements */ int set_bit_no; /* Will have only single set bit of Xor */ int i; int n = size - 2; int x = 0, y = 0; /* Get the Xor of all elements in arr[] and {1, 2 .. n} */ for (i = 1; i < size; i++) Xor ^= arr[i]; for (i = 1; i <= n; i++) Xor ^= 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 < size; i++) { if (arr[i] & set_bit_no) x = x ^ arr[i]; /*Xor of first set in arr[] */ else y = y ^ arr[i]; /*Xor of second set in arr[] */ } for (i = 1; i <= n; i++) { if (i & set_bit_no) x = x ^ i; /*Xor of first set in arr[] and {1, 2, ...n }*/ else y = y ^ i; /*Xor of second set in arr[] and {1, 2, ...n } */ } cout<< "The two repeating elements are " <<y<< " " <<x; } // Driver code int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); return 0; } // This code is contributed by rathbhupendra |
C
void printRepeating( int arr[], int size) { int xor = arr[0]; /* Will hold xor of all elements */ int set_bit_no; /* Will have only single set bit of xor */ int i; int n = size - 2; int x = 0, y = 0; /* Get the xor of all elements in arr[] and {1, 2 .. n} */ for (i = 1; i < size; i++) xor ^= arr[i]; for (i = 1; i <= n; i++) xor ^= 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 < size; i++) { if (arr[i] & set_bit_no) x = x ^ arr[i]; /*XOR of first set in arr[] */ else y = y ^ arr[i]; /*XOR of second set in arr[] */ } for (i = 1; i <= n; i++) { if (i & set_bit_no) x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/ else y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */ } printf ( "n The two repeating elements are %d & %d " , x, y); } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); getchar (); return 0; } |
JAVA
class RepeatElement { void printRepeating( int arr[], int size) { /* Will hold xor of all elements */ int xor = arr[ 0 ]; /* Will have only single set bit of xor */ int set_bit_no; int i; int n = size - 2 ; int x = 0 , y = 0 ; /* Get the xor of all elements in arr[] and {1, 2 .. n} */ for (i = 1 ; i < size; i++) xor ^= arr[i]; for (i = 1 ; i <= n; i++) xor ^= 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 < size; i++) { int a = arr[i] & set_bit_no; if (a != 0 ) x = x ^ arr[i]; /*XOR of first set in arr[] */ else y = y ^ arr[i]; /*XOR of second set in arr[] */ } for (i = 1 ; i <= n; i++) { int a = i & set_bit_no; if (a != 0 ) x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/ else y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */ } System.out.println( "The two reppeated elements are :" ); System.out.println(x + " " + y); } /* Driver program to test the above function */ public static void main(String[] args) { RepeatElement repeat = new RepeatElement(); int arr[] = { 4 , 2 , 4 , 5 , 2 , 3 , 1 }; int arr_size = arr.length; repeat.printRepeating(arr, arr_size); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python3 code to Find the # two repeating elements # in a given array def printRepeating(arr, size): # Will hold xor # of all elements xor = arr[ 0 ] n = size - 2 x = 0 y = 0 # Get the xor of all # elements in arr[] # and 1, 2 .. n for i in range ( 1 , size): xor ^ = arr[i] for i in range ( 1 , n + 1 ): xor ^ = 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 in range ( 0 , size): if (arr[i] & set_bit_no): # XOR of first # set in arr[] x = x ^ arr[i] else : # XOR of second # set in arr[] y = y ^ arr[i] for i in range ( 1 , n + 1 ): if (i & set_bit_no): # XOR of first set # in arr[] and # 1, 2, ...n x = x ^ i else : # XOR of second set # in arr[] and # 1, 2, ...n y = y ^ i print ( "The two repeating" , "elements are" , y, x) # Driver code arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 1 ] arr_size = len (arr) printRepeating(arr, arr_size) # This code is contributed # by Smitha |
C#
using System; class GFG { static void printRepeating( int []arr, int size) { /* Will hold xor of all elements */ int xor = arr[0]; /* Will have only single set bit of xor */ int set_bit_no; int i; int n = size - 2; int x = 0, y = 0; /* Get the xor of all elements in arr[] and {1, 2 .. n} */ for (i = 1; i < size; i++) xor ^= arr[i]; for (i = 1; i <= n; i++) xor ^= 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 < size; i++) { int a = arr[i] & set_bit_no; if (a != 0) /* XOR of first set in arr[] */ x = x ^ arr[i]; else /* XOR of second set in arr[] */ y = y ^ arr[i]; } for (i = 1; i <= n; i++) { int a = i & set_bit_no; if (a != 0) /* XOR of first set in arr[] and {1, 2, ...n }*/ x = x ^ i; else /* XOR of second set in arr[] and {1, 2, ...n } */ y = y ^ i; } Console.WriteLine( "The two" + " reppeated elements are :" ); Console.Write(x + " " + y); } /* Driver program to test the above function */ public static void Main() { int []arr = {4, 2, 4, 5, 2, 3, 1}; int arr_size = arr.Length; printRepeating(arr, arr_size); } } // This code is contributed by Sam007 |
PHP
<?php // PHP code to Find the // two repeating elements // in a given array function printRepeating( $arr , $size ) { $xor = $arr [0]; /* Will hold xor of all elements */ $set_bit_no ; /* Will have only single set bit of xor */ $i ; $n = $size - 2; $x = 0; $y = 0; /* Get the xor of all elements in arr[] and {1, 2 .. n} */ for ( $i = 1; $i < $size ; $i ++) $xor ^= $arr [ $i ]; for ( $i = 1; $i <= $n ; $i ++) $xor ^= $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 < $size ; $i ++) { if ( $arr [ $i ] & $set_bit_no ) $x = $x ^ $arr [ $i ]; /*XOR of first set in arr[] */ else $y = $y ^ $arr [ $i ]; /*XOR of second set in arr[] */ } for ( $i = 1; $i <= $n ; $i ++) { if ( $i & $set_bit_no ) /*XOR of first set in arr[] and {1, 2, ...n }*/ $x = $x ^ $i ; else /*XOR of second set in arr[] and {1, 2, ...n } */ $y = $y ^ $i ; } echo "n The two repeating elements are " ; echo $y . " " . $x ; } $arr = array (4, 2, 4, 5, 2, 3, 1); $arr_size = count ( $arr ); printRepeating( $arr , $arr_size ); // This code has been contributed by Rajput-Ji ?> |
Javascript
<script> function printRepeating( arr, size) { let Xor = arr[0]; /* Will hold Xor of all elements */ let set_bit_no; /* Will have only single set bit of Xor */ let i; let n = size - 2; let x = 0, y = 0; /* Get the Xor of all elements in arr[] and {1, 2 .. n} */ for (i = 1; i < size; i++) Xor ^= arr[i]; for (i = 1; i <= n; i++) Xor ^= 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 < size; i++) { if (arr[i] & set_bit_no) x = x ^ arr[i]; /*Xor of first set in arr[] */ else y = y ^ arr[i]; /*Xor of second set in arr[] */ } for (i = 1; i <= n; i++) { if (i & set_bit_no) x = x ^ i; /*Xor of first set in arr[] and {1, 2, ...n }*/ else y = y ^ i; /*Xor of second set in arr[] and {1, 2, ...n } */ } document.write( "The two repeating elements are " +y+ " " +x); } // driver code let arr = [4, 2, 4, 5, 2, 3, 1]; let arr_size = arr.length; printRepeating(arr, arr_size); // This code is contributed by jana_sayantan. </script> |
输出
The two repeating elements are 4 2
方法5（使用数组元素作为索引） 感谢Manish K.Aaawat提出的这种方法。
Traverse the array. Do following for every index i of A[].{check for sign of A[abs(A[i])] ;if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])];else // i.e., A[abs(A[i])] is negative this element (ith element of list) is a repetition}Example: A[] = {1, 1, 2, 3, 2}i=0; Check sign of A[abs(A[0])] which is A[1]. A[1] is positive, so make it negative. Array now becomes {1, -1, 2, 3, 2}i=1; Check sign of A[abs(A[1])] which is A[1]. A[1] is negative, so A[1] is a repetition.i=2; Check sign of A[abs(A[2])] which is A[2]. A[2] is positive, so make it negative. 'Array now becomes {1, -1, -2, 3, 2}i=3; Check sign of A[abs(A[3])] which is A[3]. A[3] is positive, so make it negative. Array now becomes {1, -1, -2, -3, 2}i=4; Check sign of A[abs(A[4])] which is A[2]. A[2] is negative, so A[4] is a repetition.
请注意，此方法会修改原始数组，如果不允许修改数组，则可能不是推荐的方法。
C++
#include <bits/stdc++.h> using namespace std; void printRepeating( int arr[], int size) { int i; cout << "The repeating elements are" ; for (i = 0; i < size; i++) { if (arr[ abs (arr[i])] > 0) arr[ abs (arr[i])] = -arr[ abs (arr[i])]; else cout<< " " << abs (arr[i]) << " " ; } } // Driver code int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); return 0; } // This code is contributed by rathbhupendra |
C
#include <stdio.h> #include <stdlib.h> void printRepeating( int arr[], int size) { int i; printf ( " The repeating elements are" ); for (i = 0; i < size; i++) { if (arr[ abs (arr[i])] > 0) arr[ abs (arr[i])] = -arr[ abs (arr[i])]; else printf ( " %d " , abs (arr[i])); } } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); getchar (); return 0; } |
JAVA
class RepeatElement { void printRepeating( int arr[], int size) { int i; System.out.println( "The repeating elements are : " ); for (i = 0 ; i < size; i++) { int abs_val = Math.abs(arr[i]); if (arr[abs_val] > 0 ) arr[abs_val] = -arr[abs_val]; else System.out.print(abs_val + " " ); } } /* Driver program to test the above function */ public static void main(String[] args) { RepeatElement repeat = new RepeatElement(); int arr[] = { 4 , 2 , 4 , 5 , 2 , 3 , 1 }; int arr_size = arr.length; repeat.printRepeating(arr, arr_size); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python3 code for Find the two repeating # elements in a given array def printRepeating(arr, size) : print ( " The repeating elements are" ,end = " " ) for i in range ( 0 ,size) : if (arr[ abs (arr[i])] > 0 ) : arr[ abs (arr[i])] = ( - 1 ) * arr[ abs (arr[i])] else : print ( abs (arr[i]),end = " " ) # Driver code arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 1 ] arr_size = len (arr) printRepeating(arr, arr_size) # This code is contributed by Nikita Tiwari. |
C#
// C# code for Find the two repeating // elements in a given array using System; class GFG { static void printRepeating( int []arr, int size) { int i; Console.Write( "The repeating elements are : " ); for (i = 0; i < size; i++) { int abs_val = Math.Abs(arr[i]); if (arr[abs_val] > 0) arr[abs_val] = -arr[abs_val]; else Console.Write(abs_val + " " ); } } /* Driver program to test the above function */ public static void Main() { int []arr = {4, 2, 4, 5, 2, 3, 1}; int arr_size = arr.Length; printRepeating(arr, arr_size); } } // This code is contributed by Sam007 |
PHP
<?php function printRepeating( $arr , $size ) { $i ; echo "The repeating elements are" , " " ; for ( $i = 0; $i < $size ; $i ++) { if ( $arr [ abs ( $arr [ $i ])] > 0) $arr [ abs ( $arr [ $i ])] = - $arr [ abs ( $arr [ $i ])]; else echo abs ( $arr [ $i ]), " " ; } } $arr = array (4, 2, 4, 5, 2, 3, 1); $arr_size = sizeof( $arr ); printRepeating( $arr , $arr_size ); #This code is contributed by aj_36 ?> |
Javascript
<script> function printRepeating(arr , size) { var i; document.write( "The repeating elements are : " ); for (i = 0; i < size; i++) { var abs_val = Math.abs(arr[i]); if (arr[abs_val] > 0)x arr[abs_val] = -arr[abs_val]; else document.write(abs_val + " " ); } } /* Driver program to test the above function */ var arr = [4, 2, 4, 5, 2, 3, 1]; var arr_size = arr.length; printRepeating(arr, arr_size); // This code is contributed by 29AjayKumar </script> |
输出
The repeating elements are 4 2
方法6（类似于方法5）
感谢Vivek Kumar提出的这种方法。
重点是将第（arr[i]th-1）个索引处的每个元素增加N-1（因为元素仅存在于N-2之前），同时检查该索引处的元素除以（N-1）是否得到2。如果这是真的，那么这意味着元素出现了两次，我们可以很容易地说，这是我们的答案之一。当我们想要计算时，这是非常有用的技术之一 有限距离阵元的频率 （见 这篇帖子 了解更多）。
这种方法的原理是，当一个元素的余数除以任何大于该元素的数时，该元素的余数总是相同的。类似地，当我们将（arr[i]th-1）索引处的每个元素增加N-1时，当这个增加的元素除以N-1时，它将给出我们将N-1添加到其中的次数，从而给出该索引的出现次数（根据基于1的索引）。
下面给出的代码适用于此方法：
C++
#include <iostream> using namespace std; void twoRepeated( int arr[], int N) { int m = N - 1; for ( int i = 0; i < N; i++) { arr[arr[i] % m - 1] += m; if ((arr[arr[i] % m - 1] / m) == 2) cout << arr[i] % m << " " ; } } // Driver Code int main() { int arr[] = { 4, 2, 4, 5, 2, 3, 1 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "The two repeating elements are " ; twoRepeated(arr, n); return 0; } // This code is contributed by Kartik Singh Kushwah |
JAVA
import java.io.*; class GFG{ public static void twoRepeated( int arr[], int N) { int m = N - 1 ; for ( int i = 0 ; i < N; i++) { arr[arr[i] % m - 1 ] += m; if ((arr[arr[i] % m - 1 ] / m) == 2 ) System.out.printf(arr[i] % m + " " ); } } // Driver code public static void main(String[] args) { int arr[] = { 4 , 2 , 4 , 5 , 2 , 3 , 1 }; int n = 7 ; System.out.printf( "The two repeating elements are " ); twoRepeated(arr, n); } } // This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach def twoRepeated(arr, N): m = N - 1 for i in range (N): arr[arr[i] % m - 1 ] + = m if ((arr[arr[i] % m - 1 ] / / m) = = 2 ): print (arr[i] % m ,end = " " ) # Driver Code arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 1 ] n = len (arr) print ( "The two repeating elements are " , end = "") twoRepeated(arr, n) # This code is contributed by Shubham Singh |
C#
// C# program for the above approach using System; public class GFG { public static void twoRepeated( int [] arr, int N) { int m = N - 1; for ( int i = 0; i < N; i++) { arr[arr[i] % m - 1] += m; if ((arr[arr[i] % m - 1] / m) == 2) Console.Write(arr[i] % m + " " ); } } // Driver code public static void Main(String []args) { int [] arr = { 4, 2, 4, 5, 2, 3, 1 }; int n = 7; Console.Write( "The two repeating elements are " ); twoRepeated(arr, n); } } // This code is contributed by splevel62. |
Javascript
<script> function twoRepeated(arr, N) { let m = N - 1; for (let i = 0; i < N; i++) { arr[parseInt(arr[i] % m) - 1] += m; if (parseInt(arr[parseInt(arr[i] % m) - 1] / m) == 2) document.write(parseInt(arr[i] % m) + " " ); } } // Driver Code var arr = [ 4, 2, 4, 5, 2, 3, 1 ]; var n = 7; document.write( "The two repeating elements are " ); twoRepeated(arr, n); // This code is contributed by Potta Lokesh </script> |
输出
The two repeating elements are 4 2
方法7 这里的要点是将数组元素逐个输入无序集。如果某个特定元素已经存在于集合中，那么它就是一个重复元素。
C++
// C++ program to Find the two repeating // elements in a given array #include <bits/stdc++.h> using namespace std; void printRepeating( int arr[], int size) { unordered_set< int >s; cout<< "The two Repeating elements are : " ; for ( int i=0;i<size;i++) { if (s.empty()== false && s.find(arr[i])!=s.end()) cout<<arr[i]<< " " ; s.insert(arr[i]); } } // Driver code int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printRepeating(arr, arr_size); return 0; } // This code is contributed by nakul amate |
JAVA
// Java program to Find the two repeating // elements in a given array import java.util.*; class GFG{ static void printRepeating( int arr[], int size) { HashSet<Integer>s = new HashSet<>(); System.out.print( "The two Repeating elements are : " ); for ( int i = 0 ; i < size; i++) { if (!s.isEmpty() && s.contains(arr[i])) System.out.print(arr[i]+ " " ); s.add(arr[i]); } } // Driver code public static void main(String[] args) { int arr[] = { 4 , 2 , 4 , 5 , 2 , 3 , 1 }; int arr_size = arr.length; printRepeating(arr, arr_size); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to find the two repeating # elements in a given array def printRepeating(arr, size): s = set () print ( "The two Repeating elements are : " , end = "") for i in range (size): if ( len (s) and arr[i] in s): print (arr[i], end = " " ) s.add(arr[i]) # Driver code arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 1 ] arr_size = len (arr) printRepeating(arr, arr_size) # This code is contributed by Shubham Singh |
C#
// C# program to Find the two repeating // elements in a given array using System; using System.Collections.Generic; public class GFG{ static void printRepeating( int [] arr, int size) { HashSet< int >s = new HashSet< int >(); Console.Write( "The two Repeating elements are : " ); for ( int i = 0; i < size; i++) { if (s.Count != 0 && s.Contains(arr[i])) Console.Write(arr[i] + " " ); s.Add(arr[i]); } } // Driver code public static void Main() { int [] arr = {4, 2, 4, 5, 2, 3, 1}; int arr_size = arr.Length; printRepeating(arr, arr_size); } } // This code is contributed by Shubham Singh |
Javascript
<script> function printRepeating(arr, size) { const s = new Set(); document.write( "The two repeating elements are " ); for (let i = 0; i < size; i++) { if (s.size != 0 && s.has(arr[i])) document.write(arr[i] + " " ); s.add(arr[i]); } } // Driver Code var arr = [ 4, 2, 4, 5, 2, 3, 1 ]; var arr_size = 7; printRepeating(arr, arr_size); // This code is contributed by Shubham Singh </script> |
输出
The two Repeating elements are : 4 2
时间复杂度：O（n）
辅助空间：O（n）
如果您发现上述代码/算法不正确，请写下评论，或者找到更好的方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
