刪除兩個數(shù)組中的共同元素
http://www.shnenglu.com/jake1036/archive/2011/07/01/149882.html
兩個數(shù)組是有序的，也就是說給了一定的初始信息
在 O(N) 下刪除各自共同的元素
思路
因為是有序的
對這兩個數(shù)組從高到低遍歷
檢測兩個當(dāng)前元素
如果相等，則是要刪除的對象，并且要向后查找后面相等的情況
如果不相等，提取小的那個，因為大的有可能在后面相等
這種方法不能刪除自身重復(fù)的元素
可以寫個過濾函數(shù)過濾掉重復(fù)的元素
過濾有兩個策略，一是只留一個重復(fù)的元素
二是全部刪除重復(fù)的元素
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 閱讀(485)
評論(0) 編輯 收藏 引用