在O（n）时间和O（1）额外空间中查找重复项|集1-yiteyi-C++库

给定一个由n个元素组成的数组，其中包含从0到n-1的元素，其中任何一个数字出现的次数都是任意的。在O（n）中找到这些重复的数字，并且只使用恒定的内存空间。

null

例子：

Input : n = 7 and array[] = {1, 2, 3, 6, 3, 6, 1}
Output: 1, 3, 6

Explanation: The numbers 1 , 3 and 6 appears more
than once in the array.

Input : n = 5 and array[] = {1, 2, 3, 4 ,3}
Output: 3

Explanation: The number 3 appears more than once
in the array.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

此问题是以下问题的扩展版本。 查找给定数组中的两个重复元素上述链接的方法1和方法2不适用，因为问题是O（n）时间复杂度和O（1）常数空间。此外，方法3和方法4不能在这里应用，因为在这个问题中可能有两个以上的重复元素。方法5可以扩展到解决这个问题。以下是与方法5类似的解决方案。

解决方案1：

方法： 数组中的元素从0到n-1，所有元素都是正的。所以要找出重复的元素，需要一个HashMap，但问题是要在常量空间中解决这个问题。有一个catch，数组的长度为n，元素从0到n-1（n个元素）。该数组可用作哈希映射。 问题在于下面的方法。 这种方法只适用于具有顶多 2个重复元素，即如果数组包含一个元素的2个以上重复项，则它将不起作用。例如：{1,6,3,1,3,6,6}它将输出为：1 3 6。
注：上述程序不处理0个案例（如果数组中存在0）。这个程序也可以很容易地修改来处理这个问题。处理它不是为了让代码简单。（通过向所有值添加+1（+1），可以修改程序以处理0个情况。也可以从答案中减去一，然后写下来 {arr[abs（arr[i]）–1]} （在代码中）

在下面的另一种方法中，所讨论的解决方案只打印一次重复的元素。

方法： 基本思想是使用HashMap来解决这个问题。但是有一个缺点，数组中的数字从0到n-1，输入数组的长度为n。因此，输入数组可以用作哈希映射。在遍历数组时，如果遇到元素“a”，则将第%n’个元素的值增加n。可通过将第%n’个元素除以n来检索频率。
算法：
1. 从头到尾遍历给定数组。
2. 对于数组中的每个元素，将第n个元素的arr[i]%增加n。
3. 现在再次遍历数组，并打印arr[i]/n大于1的所有索引i。这保证了数字n已经被添加到该索引中
4. 这种方法之所以有效，是因为所有元素都在0到n-1的范围内，只有当值“i”出现多次时，arr[i]才会大于n。

实施：

C++

                         // C++ code to find                       
                         // duplicates in O(n) time                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         int                                     main()                       
                         {                       
                                   
                                                 int                                     numRay[] = { 0, 4, 3, 2, 7, 8, 2, 3, 1 };                       
                                                 int                                     arr_size =                                     sizeof                                     (numRay) /                                     sizeof                                     (numRay[0]);                       
                                   
                                   
                                                 // count the frequency                       
                                                 for                                     (                                     int                                     i = 0; i < arr_size; i++) {                       
                                                 numRay[numRay[i] % arr_size]                       
                                                 = numRay[numRay[i] % arr_size] + arr_size;                       
                                                 }                       
                                                 cout <<                                     "The repeating elements are : "                                     << endl;                       
                                                 for                                     (                                     int                                     i = 0; i < arr_size; i++) {                       
                                                 if                                     (numRay[i] >= arr_size * 2) {                       
                                                 cout << i <<                                     " "                                     << endl;                       
                                                 }                       
                                                 }                       
                                                 return                                     0;                       
                         }                       
                                   
                         // This code is contributed by PrinciRaj1992                       

JAVA

                         // JAVA code to find                       
                         // duplicates in O(n) time                       
                                   
                         class                                     Leet442 {                       
                                   
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     numRay[] = {                                     0                                     ,                                     4                                     ,                                     3                                     ,                                     2                                     ,                                     7                                     ,                                     8                                     ,                                     2                                     ,                                     3                                     ,                                     1                                     };                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < numRay.length; i++) {                       
                                                 numRay[numRay[i] % numRay.length]                       
                                                 = numRay[numRay[i] % numRay.length]                       
                                                 + numRay.length;                       
                                                 }                       
                                                 System.out.println(                                     "The repeating elements are : "                                     );                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < numRay.length; i++) {                       
                                                 if                                     (numRay[i] >= numRay.length *                                     2                                     ) {                       
                                                 System.out.println(i +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       

python

                         # Python3 code to find duplicates in O(n) time                       
                         numRay                                     =                                     [                                     0                                     ,                                     4                                     ,                                     3                                     ,                                     2                                     ,                                     7                                     ,                                     8                                     ,                                     2                                     ,                                     3                                     ,                                     1                                     ]                       
                         arr_size                                     =                                     len                                     (numRay)                       
                         for                                     i                                     in                                     range                                     (arr_size):                       
                                   
                                                 x                                     =                                     numRay[i]                                     %                                     arr_size                       
                                                 numRay[x]                                     =                                     numRay[x]                                     +                                     arr_size                       
                                   
                         print                                     (                                     "The repeating elements are : "                                     )                       
                         for                                     i                                     in                                     range                                     (arr_size):                       
                                                 if                                     (numRay[i] >                                     =                                     arr_size                                     *                                     2                                     ):                       
                                                 print                                     (i,                                     " "                                     )                       
                                   
                         # This code is contributed by 29AjayKumar                       

C#

                         // C# code to find                       
                         // duplicates in O(n) time                       
                         using                                     System;                       
                         class                                     Leet442                       
                         {                       
                                                 public                                     static                                     void                                     Main(String []args)                       
                                                 {                       
                                                 int                                     []numRay = { 0, 4, 3, 2, 7, 8, 2, 3, 1 };                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < numRay.Length; i++)                       
                                                 {                       
                                                 numRay[numRay[i] % numRay.Length]                       
                                                 = numRay[numRay[i] % numRay.Length]                       
                                                 + numRay.Length;                       
                                                 }                       
                                                 Console.WriteLine(                                     "The repeating elements are : "                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < numRay.Length; i++)                       
                                                 {                       
                                                 if                                     (numRay[i] >= numRay.Length * 2)                       
                                                 {                       
                                                 Console.WriteLine(i +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by shivanisinghss2110                       

Javascript

                         <script>                       
                                                 // Javascript code to find                       
                                                 // duplicates in O(n) time                       
                                                 let numRay = [ 0, 4, 3, 2, 7, 8, 2, 3, 1 ];                       
                                                 let arr_size = numRay.length;                       
                                   
                                   
                                                 // count the frequency                       
                                                 for                                     (let i = 0; i < arr_size; i++) {                       
                                                 numRay[numRay[i] % arr_size]                       
                                                 = numRay[numRay[i] % arr_size] + arr_size;                       
                                                 }                       
                                                 document.write(                                     "The repeating elements are : "                                     +                                     "</br>"                                     );                       
                                                 for                                     (let i = 0; i < arr_size; i++) {                       
                                                 if                                     (numRay[i] >= arr_size * 2) {                       
                                                 document.write(i +                                     " "                                     +                                     "</br>"                                     );                       
                                                 }                       
                                                 }                       
                                   
                         // This code is contributed by mukesh07.                       
                         </script>                       

输出：

The repeating elements are : 
2 
3

复杂性分析：

时间复杂性： O（n）。只需要两次遍历。所以时间复杂度是O（n）。
辅助空间： O（1）。不需要额外的空间，因此空间复杂度是恒定的。

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

THE END

技术文章