淘汰數組中的重復的數
淘汰數組中的重復的數，有多種方式
1.
有序的
重復的只保留一個
2.
有序的
重復的全部淘汰
3.
無序的
連續重復的保留一個，后面如果再次出現，但是不連續，還是保留
4.
無序的
連續重復的都淘汰，后面如果在重復出現多次，也是全部淘汰，如果只出現一次，則保留
5.
無序的
考慮整個數組中，對重復的，只保留第一個，不管連續還是不連續
6.
無序的
考慮整個數組，對多次出現的，不考慮連續不連續，都淘汰
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 #include <map>
5 using namespace std;
6
7 void foo_0(int* a, int n, int& alen)
8 {
9 sort(a, a + n);
10 // foo_2(a, n, alen);
11 alen = 1;
12 for (int i = 1; i <= n - 1; ++i)
13 {
14 if (a[i] != a[i - 1])
15 {
16 a[alen++] = a[i];
17 }
18 }
19 }
20
21 void foo_1(int* a, int n, int& alen)
22 {
23 sort(a, a + n);
24 // foo_3(a, n, alen);
25 alen = 0;
26 int i = 0;
27 while (i <= n - 1)
28 {
29 if (i <= n - 2)
30 {
31 if (a[i] == a[i + 1])
32 {
33 i += 2;
34 while (i <= n - 1 && a[i] == a[i - 1])
35 {
36 ++i;
37 }
38 }
39 else
40 {
41 a[alen++] = a[i++];
42 }
43 }
44 else
45 {
46 a[alen++] = a[i++];
47 }
48 }
49 }
50
51 void foo_2(int* a, int n, int& alen)
52 {
53 alen = 1;
54 for (int i = 1; i <= n - 1; ++i)
55 {
56 if (a[i] != a[i - 1])
57 {
58 a[alen++] = a[i];
59 }
60 }
61 }
62
63 void foo_3(int* a, int n, int& alen)
64 {
65 alen = 0;
66 int i = 0;
67 while (i <= n - 1)
68 {
69 if (i <= n - 2)
70 {
71 if (a[i] == a[i + 1])
72 {
73 i += 2;
74 while (i <= n - 1 && a[i] == a[i - 1])
75 {
76 ++i;
77 }
78 }
79 else
80 {
81 a[alen++] = a[i++];
82 }
83 }
84 else
85 {
86 a[alen++] = a[i++];
87 }
88 }
89 }
90
91 void foo_4(int* a, int n, int& alen)
92 {
93 alen = 0;
94 map<int, int> m;
95 for (int i = 0; i <= n - 1; ++i)
96 {
97 ++m[a[i]];
98 }
99 for (int i = 0; i <= n - 1; ++i)
100 {
101 if (m[a[i]] == 1)
102 {
103 a[alen++] = a[i];
104 }
105 else if (m[a[i]] >= 2)
106 {
107 a[alen++] = a[i];
108 m[a[i]] = -1;
109 }
110 }
111 }
112
113 void foo_5(int* a, int n, int& alen)
114 {
115 alen = 0;
116 map<int, int> m;
117 for (int i = 0; i <= n - 1; ++i)
118 {
119 ++m[a[i]];
120 }
121 for (int i = 0; i <= n - 1; ++i)
122 {
123 if (m[a[i]] == 1)
124 {
125 a[alen++] = a[i];
126 }
127 }
128 }
129
130 void init(int*& a, int& len)
131 {
132 int t[] = {2, 2, 3, 4, 5, 2, 2, 6, 7, 8, 9, 9, 9};
133 // int t[] = {1, 1, 1, 1};
134 len = sizeof (t) / sizeof (*t);
135 delete [] a;
136 a = new int[len];
137 memcpy(a, t, sizeof (*a) * len);
138 }
139
140 void print(int a[], int n)
141 {
142 for (int i = 0; i != n; ++i)
143 {
144 cout << a[i] << ' ';
145 }
146 cout << endl;
147 }
148
149 int main()
150 {
151 int* a = 0;
152 int len = 0;
153
154 init(a, len);
155 foo_0(a, len, len);
156 print(a, len);
157
158 init(a, len);
159 print(a, len);
160
161 foo_1(a, len, len);
162 print(a, len);
163
164 init(a, len);
165 print(a, len);
166
167 foo_2(a, len, len);
168 print(a, len);
169
170 init(a, len);
171 foo_3(a, len, len);
172 print(a, len);
173
174 init(a, len);
175 print(a, len);
176 foo_4(a, len, len);
177 print(a, len);
178
179 init(a, len);
180 print(a, len);
181 foo_5(a, len, len);
182 print(a, len);
183 }
posted on 2011-07-29 00:27
unixfy 閱讀(161)
評論(0) 編輯 收藏 引用