思路就是先排序，O(NlogN)
然后一次遍历排序后的集合
在具体遍历的过程中，需要有个策略
详见代码
需要有两个相邻的滑标，比较相邻的元素是否相等
但是为了避免重复计入，需要设置一个标志位，来表示是否是组里面的第一个元素
如果相邻的两个元素不相等，则表示前面组检测结束，需要检查记录这个组的集合是否为空
若不为空，则将其加入结果中，并且要情况这个辅助组和标志位
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 void foo(vector<vector<int> >& ret, const vector<int>& dataset)
7 {
8 ret.clear();
9 if (dataset.size() <= 1)
10 {
11 return;
12 }
13 vector<int>::size_type i, j;
14 bool f = false;
15 vector<int> tmp;
16 for (i = 0, j = 1; i != dataset.size() - 1; ++i, ++j)
17 {
18 if (dataset[i] == dataset[j])
19 {
20 if (!f)
21 {
22 f = true;
23 tmp.push_back(dataset[i]);
24 tmp.push_back(dataset[j]);
25 }
26 else
27 {
28 tmp.push_back(dataset[j]);
29 }
30 }
31 else
32 {
33 if (!tmp.empty())
34 {
35 ret.push_back(tmp);
36 tmp.clear();
37 f = false;
38 }
39 }
40 }
41 }
42
43 int main()
44 {
45 vector<int> dataset;
46 for (int i = 0; i < 10; ++i)
47 {
48 dataset.push_back(i);
49 }
50 dataset.push_back(5);
51 dataset.push_back(3);
52 dataset.push_back(5);
53 dataset.push_back(8);
54 sort(dataset.begin(), dataset.end());
55
56 vector<vector<int> > ret;
57 foo(ret, dataset);
58 for (vector<vector<int> >::size_type i = 0; i != ret.size(); ++i)
59 {
60 for (vector<int>::size_type j = 0; j != ret[i].size(); ++j)
61 {
62 cout << ret[i][j] << ' ';
63 }
64 cout << endl;
65 }
66
67 return 0;
68 }
69
posted on 2011-07-11 13:53
unixfy 阅读(260)
评论(0) 编辑 收藏 引用