问题描述：
Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )
You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo
解答：
借鉴俄罗斯方块的玩法，先给个直观的例子。对于数组 4 3 3 2 1 2 3 4 4 7，按照类俄罗斯方块的玩法，当7要往下落的时候，屏幕上会呈现这个场景
4
4 3 2
4 3 2 1 _
当7落下时，获得了
4
4 3 2
4 3 2 1 7
此时最后一行元素数目满了（最后一行的大小为5），将其删除，继续落数字。直到所有数字都落下来了。此时数目超过n/5的元素一定在最后一行（因为假设数字a的个数超过n/5，删除操作最多执行了n/5次，所以最后必然a还在最后一行中）。但是，最后一行中的元素也有可能不是我们要的。此时需要扫描一下来确定。
同样的算法对于任意的m（m为正整数）均适用。
给出代码：
1: #include <iostream>
2: #include <map>
3: #include <algorithm>
4: typedef std::map<int, int> Map;
5: Map findOverNth(int arr[], int size, int n)
6: {
7: Map ret_map;
8: typedef Map::value_type Elem; //pair<CONST int, int>
9: int total = 0;
10: std::for_each(arr, arr + size, [&, n](int val)
11: {
12: auto ret_pair = ret_map.insert(Elem(val, 0));
13: ++(*ret_pair.first).second; ++ total;
14: if (ret_map.size() == n)
15: for (auto iter = ret_map.begin(); iter != ret_map.end(); )
16: {
17: --(*iter).second; -- total;
18: if ((*iter).second == 0)
19: ret_map.erase(iter++);
20: else
21: iter++;
22: }
23: });
24: std::for_each(ret_map.begin(), ret_map.end(), [](Elem &elem) {elem.second = 0;});
25: std::for_each(arr, arr + size, [&ret_map](int val) {if (ret_map.find(val) != ret_map.end()) ret_map[val] ++;});
26: for (auto iter = ret_map.begin(); iter != ret_map.end(); )
27: {
28: if ((*iter).second <= size / n)
29: ret_map.erase(iter++);
30: else
31: iter++;
32: }
33: return ret_map;
34: }
35: using namespace std;
36: int main()
37: {
38: //int arr[] = {5,6,7,8, 10, 4,4, 4, 4,1, 1,1};
39: int arr[] = {5,6,7,8, 10, 10, 10,10,10,10, 4,4, 4, 4,4,1, 1,1,1};
40: auto a_map = findOverNth(arr, sizeof(arr)/sizeof(int), 4);
41: cout<<sizeof(arr)/sizeof(int)<<endl;
42: //cout<<a_map.size()<<endl;
43: for each(auto elem in a_map)
44: {
45: cout<<elem.first<<" "<<elem.second<<endl;
46: }
47: }