Leetcode上面有这么一道难度为easy的算法题：找出一个长度为n的数组中，重复次数超过一半的数，假设这样的数一定存在。O(n²)和O(nlog(n))(二叉树插入)的算法比较直观。Boyer–Moore majority vote algorithm在1980年提出，用O(1)空间和O(n)时间解决了这个问题。这个算法的思路：由于重复频率超过 floor(n/2)的数字只有一个，等价于与其余数字出现频率的差大于零。当遍历整个数组时，使用变量candidate记录当前重复次数最多的数，count计算candidate重复多余的次数。以下为具体实现：

int count = 0;int candidate;for(int i = 0; i < n; ++i){  if(count == 0)  {     candidate = a[i];    }

if(candidate == a[i]) 　　　++count; 　else 　　  --count;}

在遍历过程中，当前元素与candidate相同则投支持票，否则投反对票。当count状态为0时，说明之前的子数组中不存在重复次数超过一半的数，遍历余下的数组成为原问题的子问题。若该数不一定存在，那么需要再一次遍历数组，鉴证找到的元素是否符合条件。

 

进一步思考，若要返回出现次数大于k次的所有元素，即为iceburg query问题。iceburg query的想法其实可以向其名字一样形象。假设将数组中所有元素转化为histogram，高度为出现的频率，那么每个筒子有高有低，就像冰山一样。之后不断的下降冰山，下降k次。那么剩下还留在水面上的就是满足要求的元素。直接这样求解问题需要多次遍历数组内的元素O(log(n!) + log(nk))。

当然也可以遍历两次。由于满足条件的元素出现次数大于k，那么整个数组中至多存在n/k个。因此在第一次遍历的时候，维护一个数组a，若当前元素不存在数组中，则插入该元素和出现次数1。然后判断数组大小是否超过n/k。如果超过则所有元素下降一个，并且除去出现次数为0的元素。第二次遍历，查看是否a中的元素出现次数都大于k（因为满足条件的元素个数可以小于n/k）。

unordered_map m; // first pass for(i = 0; i < n; ++i) {
   　　if(m.find(nums[i]) == m.end()) 　　{
   　　　　m.insert(pair
     
      (nums[i], 1)); 　　} 　　else 　　{
   　　　　++m[ nums[i] ]; 　　} 　　if(m.size() > n / k) 　　{
   　　　　for(auto it = m.begin(); it != m.end();++it) 　　　　{
   　　　　　　--(it -> second); 　　　　　　if(!(it -> second)) 　　　　　　　　m.erase(it++); 　　　　} 　　} } // second pass for(auto &x: m) 　　m -> second = 0; for(i = 0; i < n; ++i) {
   　　++m[ nums[i] ]; 　　if(m[nums[i]] > k) 　　{
   　　　　v.push_back(nums[i]); 　　} }