数组中重复出现的数字
标签:根据 用两个 lse pre turn array span \n window
代码实现的不同方法用(#if 0 ..... #endif)注释
1 #include 2 #include 3 #if 0
4 //这种方法使用两个指针来遍历数组,运用两个for循环,时间复杂度为O(n^2),空间复杂度为O(1)
5 void test()
6 {
7 int array[7] = { 0, 3, 1, 0, 2, 5, 3 };
8 int i = 0;
9 for (i = 0; i 7;i++)
10 {
11 int j = i + 1;
12 for (; j 7; j++)
13 {
14 if (array[i] == array[j])
15 {
16 printf("重复的数字为:%d \n", array[i]);
17 return;
18 }
19 }
20 }
21 if (i>=7)
22 printf("没找到重复的数字\n");
23 }
24 #endif
25 #if 0
26 //这种方法是先通过冒泡排序将数组排序,时间复杂度为O(n^2),空间复杂度为O(1);
27 void test()
28 {
29 int array[7] = { 2, 3, 1, 0, 2, 5, 3 };
30 int i = 0;
31 for (i = 0; i sizeof(array) / sizeof(array[0]); i++)
32 {
33 int j = 0;
34 for (j = 0; j )
35 {
36 if (array[j] > array[i])
37 {
38 int temp = array[j];
39 array[j] = array[i];
40 array[i] = temp;
41 }
42 }
43 }
44 for (i = 0; i 6; i++)
45 {
46 if (array[i] == array[i + 1])
47 {
48 printf("重复出现的数字为:");
49 printf("%d ", array[i]);
50 }
51 }
52 }
53 #endif
54 //这种方法使用折半插入排序对数组进行排序
55 //比较次数虽然为nlog(n)(以2为底),但是时间复杂度任然为O(N^2);
56
57 void test()
58 {
59 int array[7] = { 0, 3, 1, 0, 2, 5, 3 };
60 int i = 2;
61 for (i = 2; i sizeof(array) / sizeof(array[0]); i++)
62 {
63 int low = 1; int high = i - 1;
64 int temp = array[i];
65 while (low high)
66 {
67 int mid = (high - low) / 2 + low;
68 if (temp array[mid])
69 high = mid - 1;
70 else
71 low = mid + 1;
72 }
73 //移动元素
74 int j = 0;
75 for (j = i - 1; j>=low; j--)
76 {
77 array[j + 1] = array[j];
78 }
79 array[low] = temp;
80 }
81 for (i = 0; i sizeof(array)/sizeof(array[0])-1; i++)
82 {
83 if (array[i] == array[i + 1])
84 {
85 printf("重复出现的数字为:");
86 printf("%d ", array[i]);
87 }
88 }
89 }
90
91 int main()
92 {
93 test();
94 system("pause");
95 return 0;
96 }
97 //在提一种思路,如果数组中的元素已经排好序了,则它的元素应该与它的下标相同,可以根据这个
98 //方法实现快速的排序,从而找到重复的数字,当然,这种方法只针对特殊情况。
99 //代码中尽管有两重循环,但每个数字最多只要交换两次就能找到属于它的位置,因此总的时间复杂度为O(n),
100 //空间复杂度为O(1);
101 #if 0
102 bool duplicate(int numbers[], int *temp, int length)
103 {
104 if (numbers == NULL || length 0)
105 return false;
106 for (int i = 0; i )
107 {
108 if (numbers[i]0 || numbers[i]>length - 1)
109 return false;
110 }
111 for (int i = 0; i )
112 {
113 while (numbers[i] != i)
114 {
115 if (numbers[i] == numbers[numbers[i]])
116 {
117 *temp = numbers[i];
118 return true;
119 }
120 //交换numbers[i]与numbers[numbers[i]]
121 int t = numbers[i];
122 numbers[i] = numbers[numbers[i]];
123 numbers[numbers[i]] = t;
124 }
125 }
126 }
127 #endif
数组中重复出现的数字
标签:根据 用两个 lse pre turn array span \n window
原文地址:https://www.cnblogs.com/love-you1314/p/9750664.html
评论