删除两个数组中的共同元素
http://www.cppblog.com/jake1036/archive/2011/07/01/149882.html
两个数组是有序的，也就是说给了一定的初始信息
在 O(N) 下删除各自共同的元素
思路
因为是有序的
对这两个数组从高到低遍历
检测两个当前元素
如果相等，则是要删除的对象，并且要向后查找后面相等的情况
如果不相等，提取小的那个，因为大的有可能在后面相等
这种方法不能删除自身重复的元素
可以写个过滤函数过滤掉重复的元素
过滤有两个策略，一是只留一个重复的元素
二是全部删除重复的元素
1 #include <iostream>
2 using namespace std;
3
4 void foo(int a[], int b[], int an, int bn, int& alen, int& blen)
5 {
6 int i = 0, j = 0;
7 int u = 0, v = 0;
8 while (i != an && j != bn)
9 {
10 if (a[i] == b[j])
11 {
12 ++i;
13 ++j;
14 while (i != an && a[i] == a[i - 1])
15 {
16 ++i;
17 }
18 while (j != bn && b[j] == b[j - 1])
19 {
20 ++j;
21 }
22 }
23 else if (a[i] < b[j])
24 {
25 a[u++] = a[i++];
26 }
27 else
28 {
29 b[v++] = b[j++];
30 }
31 }
32 while (i != an)
33 {
34 a[u++] = a[i++];
35 }
36 while (j != bn)
37 {
38 b[v++] = b[j++];
39 }
40 alen = u;
41 blen = v;
42 }
43
44 void filter(int a[], int n, int& t)
45 {
46 t = 0;
47 bool f = false;
48 for (int i = 0; i != n - 1; ++i)
49 {
50 if (a[i] == a[i + 1])
51 {
52 }
53 else
54 {
55 a[t++] = a[i];
56 }
57 }
58 }
59
60 int main()
61 {
62 int a[] = {1, 3, 6, 6, 6, 7, 7, 8, 9, 14, 15, 20, 22};
63 int b[] = {2, 3, 3, 7, 15, 15, 17, 19, 20, 20};
64 int alen, blen;
65 foo(a, b, sizeof (a) / sizeof (*a), sizeof (b) / sizeof (*b), alen, blen);
66
67 filter(a, alen, alen);
68 filter(b, blen, blen);
69
70 for (int i = 0; i != alen; ++i)
71 {
72 cout << a[i] << ' ';
73 }
74 cout << endl;
75 for (int i = 0; i != blen; ++i)
76 {
77 cout << b[i] << ' ';
78 }
79 cout << endl;
80 }
81
posted on 2011-07-28 17:51
unixfy 阅读(454)
评论(0) 编辑 收藏 引用