在O（n）时间内通过使用O（1）额外空间| Set-3在数组中复制-yiteyi-C++库

给定一个由n个元素组成的数组，其中包含从0到n-1的元素，其中任何一个数字出现的次数都是任意的。在O（n）中找到这些重复的数字，并且只使用恒定的内存空间。要求保持元素重复的顺序。如果没有重复元素，则打印-1。 例如：

null

Input : arr[] = {1, 2, 3, 1, 3, 6, 6}Output : 1, 3, 6Elements 1, 3 and 6 are repeating.Second occurrence of 1 is foundfirst followed by repeated occurrenceof 3 and 6.Input : arr[] = {0, 3, 1, 3, 0}Output : 3, 0Second occurrence of 3 is foundfirst followed by second occurrence of 0.

建议：请在 “实践” 首先，在进入解决方案之前。

我们在下面的帖子中讨论了解决这个问题的两种方法：在O（n）时间和O（1）额外空间中查找重复项|集1 在O（n）时间内通过使用O（1）额外空间| Set-2在数组中复制第一种方法存在问题。它会多次打印重复的数字。例如：{1,6,3,1,3,6,6}它将输出为：36。在第二种方法中，尽管每个重复的项目只打印一次，但它们的重复顺序并没有得到保持。为了按元素重复的顺序打印元素，修改了第二种方法。为了标记数组元素大小的存在，n被添加到与数组元素arr[i]相对应的索引位置arr[i]。在添加n之前，检查索引arr[i]处的值是否大于或等于n。如果大于或等于，则表示元素arr[i]在重复。为避免多次打印重复元素，请检查它是否是arr[i]的第一次重复。如果索引位置arr[i]的值小于2*n，这是第一次重复。这是因为，如果元素arr[i]在此之前只出现过一次，那么n只被添加到索引arr[i]中一次，因此索引arr[i]的值小于2*n。将n添加到索引arr[i]中，使值大于或等于2*n，这将阻止当前重复元素的进一步打印。此外，如果索引arr[i]处的值小于n，则它是元素arr[i]的第一次出现（不是重复）。所以要在索引arr[i]处标记这个add n to元素。以下是上述方法的实施情况：

C++

                         // C++ program to print all elements that                       
                         // appear more than once.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find repeating elements                       
                         void                                     printDuplicates(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     i;                       
           
                                                 // Flag variable used to                       
                                                 // represent whether repeating                       
                                                 // element is found or not.                       
                                                 int                                     fl = 0;                       
           
                                                 for                                     (i = 0; i < n; i++) {                       
           
                                                 // Check if current element is                       
                                                 // repeating or not. If it is                       
                                                 // repeating then value will                       
                                                 // be greater than or equal to n.                       
                                                 if                                     (arr[arr[i] % n] >= n) {                       
           
                                                 // Check if it is first                       
                                                 // repetition or not. If it is                       
                                                 // first repetition then value                       
                                                 // at index arr[i] is less than                       
                                                 // 2*n. Print arr[i] if it is                       
                                                 // first repetition.                       
                                                 if                                     (arr[arr[i] % n] < 2 * n) {                       
                                                 cout << arr[i] % n <<                                     " "                                     ;                       
                                                 fl = 1;                       
                                                 }                       
                                                 }                       
           
                                                 // Add n to index arr[i] to mark                       
                                                 // presence of arr[i] or to                       
                                                 // mark repetition of arr[i].                       
                                                 arr[arr[i] % n] += n;                       
                                                 }                       
           
                                                 // If flag variable is not set                       
                                                 // then no repeating element is                       
                                                 // found. So print -1.                       
                                                 if                                     (!fl)                       
                                                 cout <<                                     "-1"                                     ;                       
                         }                       
           
                         // Driver Function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 6, 3, 1, 3, 6, 6 };                       
                                                 int                                     arr_size =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 printDuplicates(arr, arr_size);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print all elements                       
                         // that appear more than once.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Function to find repeating elements                       
                         static                                     void                                     printDuplicates(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     i;                       
           
                                                 // Flag variable used to                       
                                                 // represent whether repeating                       
                                                 // element is found or not.                       
                                                 int                                     fl =                                     0                                     ;                       
           
                                                 for                                     (i =                                     0                                     ; i < n; i++)                       
                                                 {                       
           
                                                 // Check if current element is                       
                                                 // repeating or not. If it is                       
                                                 // repeating then value will                       
                                                 // be greater than or equal to n.                       
                                                 if                                     (arr[arr[i] % n] >= n)                       
                                                 {                       
           
                                                 // Check if it is first                       
                                                 // repetition or not. If it is                       
                                                 // first repetition then value                       
                                                 // at index arr[i] is less than                       
                                                 // 2*n. Print arr[i] if it is                       
                                                 // first repetition.                       
                                                 if                                     (arr[arr[i] % n] <                                     2                                     * n)                       
                                                 {                       
                                                 System.out.print( arr[i] % n +                                     " "                                     );                       
                                                 fl =                                     1                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Add n to index arr[i] to mark                       
                                                 // presence of arr[i] or to                       
                                                 // mark repetition of arr[i].                       
                                                 arr[arr[i] % n] += n;                       
                                                 }                       
           
                                                 // If flag variable is not set                       
                                                 // then no repeating element is                       
                                                 // found. So print -1.                       
                                                 if                                     (!(fl >                                     0                                     ))                       
                                                 System.out.println(                                     "-1"                                     );                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     6                                     ,                                     3                                     ,                                     1                                     ,                                     3                                     ,                                     6                                     ,                                     6                                     };                       
                                                 int                                     arr_size = arr.length;                       
                                                 printDuplicates(arr, arr_size);                       
                         }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

Python 3

                         # Python 3 program to print all elements that                       
                         # appear more than once.                       
           
                         # Function to find repeating elements                       
                         def                                     printDuplicates(arr, n):                       
           
                                                 # Flag variable used to                       
                                                 # represent whether repeating                       
                                                 # element is found or not.                       
                                                 fl                                     =                                     0                                     ;                       
           
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
           
                                                 # Check if current element is                       
                                                 # repeating or not. If it is                       
                                                 # repeating then value will                       
                                                 # be greater than or equal to n.                       
                                                 if                                     (arr[arr[i]                                     %                                     n] >                                     =                                     n):                       
           
                                                 # Check if it is first                       
                                                 # repetition or not. If it is                       
                                                 # first repetition then value                       
                                                 # at index arr[i] is less than                       
                                                 # 2*n. Print arr[i] if it is                       
                                                 # first repetition.                       
                                                 if                                     (arr[arr[i]                                     %                                     n] <                                     2                                     *                                     n):                       
                                                 print                                     (arr[i]                                     %                                     n, end                                     =                                     " "                                     )                       
                                                 fl                                     =                                     1                                     ;                       
           
                                                 # Add n to index arr[i] to mark                       
                                                 # presence of arr[i] or to                       
                                                 # mark repetition of arr[i].                       
                                                 arr[arr[i]                                     %                                     n]                                     +                                     =                                     n;                       
           
                                                 # If flag variable is not set                       
                                                 # then no repeating element is                       
                                                 # found. So print -1.                       
                                                 if                                     (fl                                     =                                     =                                     0                                     ):                       
                                                 print                                     (                                     "-1"                                     )                       
           
                         # Driver Function                       
                         arr                                     =                                     [                                     1                                     ,                                     6                                     ,                                     3                                     ,                                     1                                     ,                                     3                                     ,                                     6                                     ,                                     6                                     ];                       
                         arr_size                                     =                                     len                                     (arr);                       
                         printDuplicates(arr, arr_size);                       
           
                         # This code is contributed                       
                         # by Akanksha Rai                       

C#

                         // C# program to print all elements                       
                         // that appear more than once.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Function to find repeating elements                       
                         static                                     void                                     printDuplicates(                                     int                                     []arr,                                     int                                     n)                       
                         {                       
                                                 int                                     i;                       
           
                                                 // Flag variable used to                       
                                                 // represent whether repeating                       
                                                 // element is found or not.                       
                                                 int                                     fl = 0;                       
           
                                                 for                                     (i = 0; i < n; i++)                       
                                                 {                       
           
                                                 // Check if current element is                       
                                                 // repeating or not. If it is                       
                                                 // repeating then value will                       
                                                 // be greater than or equal to n.                       
                                                 if                                     (arr[arr[i] % n] >= n)                       
                                                 {                       
           
                                                 // Check if it is first                       
                                                 // repetition or not. If it is                       
                                                 // first repetition then value                       
                                                 // at index arr[i] is less than                       
                                                 // 2*n. Print arr[i] if it is                       
                                                 // first repetition.                       
                                                 if                                     (arr[arr[i] % n] < 2 * n)                       
                                                 {                       
                                                 Console.Write( arr[i] % n +                                     " "                                     );                       
                                                 fl = 1;                       
                                                 }                       
                                                 }                       
           
                                                 // Add n to index arr[i] to mark                       
                                                 // presence of arr[i] or to                       
                                                 // mark repetition of arr[i].                       
                                                 arr[arr[i] % n] += n;                       
                                                 }                       
           
                                                 // If flag variable is not set                       
                                                 // then no repeating element is                       
                                                 // found. So print -1.                       
                                                 if                                     (!(fl > 0))                       
                                                 Console.Write(                                     "-1"                                     );                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main ()                       
                         {                       
                                                 int                                     []arr = { 1, 6, 3, 1, 3, 6, 6 };                       
                                                 int                                     arr_size = arr.Length;                       
                                                 printDuplicates(arr, arr_size);                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by 29AjayKumar                       

PHP

                         <?php                       
                         // PHP program to print all elements that                       
                         // appear more than once.                       
           
                         // Function to find repeating elements                       
                         function                                     printDuplicates(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 $i                                     ;                       
           
                                                 // Flag variable used to                       
                                                 // represent whether repeating                       
                                                 // element is found or not.                       
                                                 $fl                                     = 0;                       
           
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
           
                                                 // Check if current element is                       
                                                 // repeating or not. If it is                       
                                                 // repeating then value will                       
                                                 // be greater than or equal to n.                       
                                                 if                                     (                                     $arr                                     [                                     $arr                                     [                                     $i                                     ] %                                     $n                                     ] >=                                     $n                                     )                       
                                                 {                       
           
                                                 // Check if it is first                       
                                                 // repetition or not. If it is                       
                                                 // first repetition then value                       
                                                 // at index arr[i] is less than                       
                                                 // 2*n. Print arr[i] if it is                       
                                                 // first repetition.                       
                                                 if                                     (                                     $arr                                     [                                     $arr                                     [                                     $i                                     ] %                                     $n                                     ] < 2 *                                     $n                                     )                       
                                                 {                       
                                                 echo                                     $arr                                     [                                     $i                                     ] %                                     $n                                     .                                     " "                                     ;                       
                                                 $fl                                     = 1;                       
                                                 }                       
                                                 }                       
           
                                                 // Add n to index arr[i] to mark                       
                                                 // presence of arr[i] or to                       
                                                 // mark repetition of arr[i].                       
                                                 $arr                                     [                                     $arr                                     [                                     $i                                     ] %                                     $n                                     ] +=                                     $n                                     ;                       
                                                 }                       
           
                                                 // If flag variable is not set                       
                                                 // then no repeating element is                       
                                                 // found. So print -1.                       
                                                 if                                     (!                                     $fl                                     )                       
                                                 echo                                     "-1"                                     ;                       
                         }                       
           
                         // Driver Function                       
                         $arr                                     =                                     array                                     (1, 6, 3, 1, 3, 6, 6);                       
                         $arr_size                                     = sizeof(                                     $arr                                     );                       
                         printDuplicates(                                     $arr                                     ,                                     $arr_size                                     );                       
           
                         // This code is contributed                       
                         // by Mukul Singh                       

Javascript

                         <script>                       
           
                         // JavaScript program to print all elements that                       
                         // appear more than once.                       
           
                         // Function to find repeating elements                       
                         function                                     printDuplicates(arr, n)                       
                         {                       
                                                 let i;                       
           
                                                 // Flag variable used to                       
                                                 // represent whether repeating                       
                                                 // element is found or not.                       
                                                 let fl = 0;                       
           
                                                 for                                     (i = 0; i < n; i++) {                       
           
                                                 // Check if current element is                       
                                                 // repeating or not. If it is                       
                                                 // repeating then value will                       
                                                 // be greater than or equal to n.                       
                                                 if                                     (arr[arr[i] % n] >= n) {                       
           
                                                 // Check if it is first                       
                                                 // repetition or not. If it is                       
                                                 // first repetition then value                       
                                                 // at index arr[i] is less than                       
                                                 // 2*n. Print arr[i] if it is                       
                                                 // first repetition.                       
                                                 if                                     (arr[arr[i] % n] < 2 * n) {                       
                                                 document.write(arr[i] % n +                                     " "                                     );                       
                                                 fl = 1;                       
                                                 }                       
                                                 }                       
           
                                                 // Add n to index arr[i] to mark                       
                                                 // presence of arr[i] or to                       
                                                 // mark repetition of arr[i].                       
                                                 arr[arr[i] % n] += n;                       
                                                 }                       
           
                                                 // If flag variable is not set                       
                                                 // then no repeating element is                       
                                                 // found. So print -1.                       
                                                 if                                     (!fl)                       
                                                 document.write(                                     "-1"                                     );                       
                         }                       
           
                         // Driver Function                       
                                   
                                                 let arr = [ 1, 6, 3, 1, 3, 6, 6 ];                       
                                                 let arr_size = arr.length;                       
                                                 printDuplicates(arr, arr_size);                       
           
                         // This code is contributed by Surbhi Tyagi.                       
           
                         </script>                       

输出：

1 3 6

时间复杂性： O（n） 辅助空间： O（1）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章