线性时间常数空间找到数组中数目超过n/5的所有元素

问题描述:

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:  }

上一篇:常见模板


下一篇:[SL] Silverlight + WCF Demo项目