给定一个包含从0到n-1元素的n个元素的数组，其中任何一个数字出现任意次数，在O（n）中找到这些重复的数字，只使用恒定的内存空间。
null
例子：
Input: n = 7 , array = {1, 2, 3, 1, 3, 6, 6}Output: 1, 3 and 6.Explanation: Duplicate element in the array are 1 , 3 and 6Input: n = 6, array = {5, 3, 1, 3, 5, 5}Output: 3 and 5.Explanation: Duplicate element in the array are 3 and 6
我们在下面的帖子中讨论了解决这个问题的方法： 在O（n）中的数组中复制，并使用O（1）额外空间| Set-2 . 但上述方法存在一个问题。它会多次打印重复的数字。
我们强烈建议您在继续解决方案之前单击此处并进行练习。
方法 : 基本思想是使用HashMap来解决这个问题。但是有一个缺点，数组中的数字从0到n-1，输入数组的长度为n。因此，输入数组可以用作哈希映射。在遍历数组时，如果元素 A. 然后增加 a%n “th元素除以n。可以通过除以 a%n 第n个元素。
算法 :
- 从头到尾遍历给定数组。
- 对于数组中的每个元素，增量 arr[i]%n 第n个元素。
- 现在再次遍历数组，并打印我为其创建的所有索引 arr[i]/n 大于1。这就保证了 N 已添加到该索引中。
注： 这种方法之所以有效，是因为所有元素都在0到n-1的范围内，只有当值“i”出现多次时，arr[i]/n才会大于1。
以下是上述方法的实施情况：
CPP
// C++ program to print all elements that // appear more than once. #include <iostream> using namespace std; // function to find repeating elements void printRepeating( int arr[], int n) { // First check all the values that are // present in an array then go to that // values as indexes and increment by // the size of array for ( int i = 0; i < n; i++) { int index = arr[i] % n; arr[index] += n; } // Now check which value exists more // than once by dividing with the size // of array for ( int i = 0; i < n; i++) { if ((arr[i] / n) >= 2) cout << i << " " ; } } // Driver code int main() { int arr[] = { 1, 6, 3, 1, 3, 6, 6 }; int arr_size = sizeof (arr) / sizeof (arr[0]); cout << "The repeating elements are: " ; // Function call printRepeating(arr, arr_size); return 0; } |
JAVA
// Java program to print all elements that // appear more than once. import java.util.*; class GFG { // function to find repeating elements static void printRepeating( int arr[], int n) { // First check all the values that are // present in an array then go to that // values as indexes and increment by // the size of array for ( int i = 0 ; i < n; i++) { int index = arr[i] % n; arr[index] += n; } // Now check which value exists more // than once by dividing with the size // of array for ( int i = 0 ; i < n; i++) { if ((arr[i] / n) >= 2 ) System.out.print(i + " " ); } } // Driver code public static void main(String args[]) { int arr[] = { 1 , 6 , 3 , 1 , 3 , 6 , 6 }; int arr_size = arr.length; System.out.println( "The repeating elements are: " ); // Function call printRepeating(arr, arr_size); } } |
Python3
# Python3 program to # print all elements that # appear more than once. # function to find # repeating elements def printRepeating(arr, n): # First check all the # values that are # present in an array # then go to that # values as indexes # and increment by # the size of array for i in range ( 0 , n): index = arr[i] % n arr[index] + = n # Now check which value # exists more # than once by dividing # with the size # of array for i in range ( 0 , n): if (arr[i] / n) > = 2 : print (i, end = " " ) # Driver code arr = [ 1 , 6 , 3 , 1 , 3 , 6 , 6 ] arr_size = len (arr) print ( "The repeating elements are:" ) # Function call printRepeating(arr, arr_size) # This code is contributed # by Shreyanshi Arun. |
C#
// C# program to print all elements that // appear more than once. using System; class GFG { // function to find repeating elements static void printRepeating( int [] arr, int n) { // First check all the values that are // present in an array then go to that // values as indexes and increment by // the size of array for ( int i = 0; i < n; i++) { int index = arr[i] % n; arr[index] += n; } // Now check which value exists more // than once by dividing with the size // of array for ( int i = 0; i < n; i++) { if ((arr[i] / n) >= 2) Console.Write(i + " " ); } } // Driver code public static void Main() { int [] arr = { 1, 6, 3, 1, 3, 6, 6 }; int arr_size = arr.Length; Console.Write( "The repeating elements are: " + "" ); // Function call printRepeating(arr, arr_size); } } |
PHP
<?php // PHP program to print all // elements that appear more // than once. // function to find // repeating elements function printRepeating( $arr , $n ) { // First check all the values // that are present in an array // then go to that values as indexes // and increment by the size of array for ( $i = 0; $i < $n ; $i ++) { $index = $arr [ $i ] % $n ; $arr [ $index ] += $n ; } // Now check which value // exists more than once // by dividing with the // size of array for ( $i = 0; $i < $n ; $i ++) { if (( $arr [ $i ] / $n ) >= 2) echo $i , " " ; } } // Driver code $arr = array (1, 6, 3, 1, 3, 6, 6); $arr_size = sizeof( $arr ) / sizeof( $arr [0]); echo "The repeating elements are: " ; // Function call printRepeating( $arr , $arr_size ); // This code is contributed by nitin mittal. ?> |
Javascript
<script> // Javascript program to print all elements that // appear more than once. // function to find repeating elements function printRepeating(arr,n) { // First check all the values that are // present in an array then go to that // values as indexes and increment by // the size of array for (let i = 0; i < n; i++) { let index = arr[i] % n; arr[index] += n; } // Now check which value exists more // than once by dividing with the size // of array for (let i = 0; i < n; i++) { if ((arr[i] / n) >= 2) document.write(i + " " ); } } // Driver code let arr=[1, 6, 3, 1, 3, 6, 6]; let arr_size = arr.length; document.write( "The repeating elements are: <br>" ); // Function call printRepeating(arr, arr_size); // This code is contributed by avanitrachhadiya2155 </script> |
输出
The repeating elements are: 1 3 6
复杂性分析 :
- 时间复杂性： O（n）。 只需要两次遍历。所以时间复杂度是O（n）
- 辅助空间： O（1）。 因为不需要额外的空间，所以空间复杂度是恒定的
本文由 萨希尔·查布拉（阿克库） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
