思路就是先排序，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) 編輯 收藏 引用