8、【常见算法】查找数组中重复元素

 1 //一个大小为n的数组，里面的数都属于范围[0, n-1]，
 2 //有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。
 3 #include <iostream>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 //交换两个数
 9 int Swap(int &a, int &b)
10 {
11     int tmp = a;
12     a = b;
13     b = tmp;
14 }
15 
16 //解法1 只能应对数组中只有一个重复元素的情况
17 int findNotReaptedNum(int *arr, int len)
18 {
19     if(!arr || len < 0)
20         cout << "Invalid Input" << endl;
21     for(int i = 0; i < len; i++)
22     {
23         while(arr[i] != i)
24         {
25             if(arr[i] == arr[arr[i]])
26                 return arr[i];
27             Swap(arr[i], arr[arr[i]]);
28         }
29     }
30     return -1;
31 }
32 //打印数组
33 void printArray(int *arr, int len)
34 {
35     if(!arr || len < 0)
36         cout << "Invalid Input" << endl;
37     for(int iter = 0; iter < len; iter++)
38     {
39         cout << arr[iter] << endl;
40     }
41 }
42 
43 int main()
44 {
45     const int arrMax = 10;
46     int arr[arrMax] = {2,5,3,5,6,7,8,9,10,1};
47     printArray(arr, arrMax);
48     cout << "数组中的重复元素为： " << findNotReaptedNum(arr, arrMax) << endl;
49 
50     return 0;
51 }

 1 //一个大小为n的数组，里面的数都属于范围[0, n-1]，
 2 //有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。
 3 #include <iostream>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 //交换两个数
 9 int Swap(int &a, int &b)
10 {
11     int tmp = a;
12     a = b;
13     b = tmp;
14 }
15 
16 //解法2
17 int findNotReaptedNum(int *arr, int len)
18 {
19     if(!arr || len < 0)
20         cout << "Invalid Input" << endl;
21     for(int i = 0; i < len; i++)
22     {
23         if(arr[i] > 0)
24         {
25             if(arr[arr[i]] < 0)
26                 return arr[i];
27             arr[arr[i]] = -arr[arr[i]];
28         }
29         else
30         {
31             if(arr[-arr[i]] < 0)
32                 return -arr[i];
33             arr[-arr[i]] = -arr[-arr[i]];
34         }
35     }
36     return -1;
37 }
38 
39 //打印数组
40 void printArray(int *arr, int len)
41 {
42     if(!arr || len < 0)
43         cout << "Invalid Input" << endl;
44     for(int iter = 0; iter < len; iter++)
45     {
46         cout << arr[iter] << endl;
47     }
48 }
49 
50 int main()
51 {
52     const int arrMax = 10;
53     int arr[arrMax] = {2,5,3,5,6,7,8,9,10,1};
54     printArray(arr, arrMax);
55     cout << "数组中的重复元素为： " << findNotReaptedNum(arr, arrMax) << endl;
56 
57     return 0;
58 }