给定一个int[]数组，给定一个整数k，打印所有出现次数大于N/k的数，没有的话，给出提示信息。

===

核心思想：一次在数组中删除K个不同的数，不停的删除，直到剩下的数的种类不足K就停止删除，那么如果一个数在数组中出现的次数大于N/K，则这个数最后一定会被剩下来。

解法：设立（K-1）个候选cand，以及（K-1）个times统计。

过程如下：

　　遍历到arr[i]时，看arr[i]是否与以及被选出来的某一个候选相同，

　　　　如果与某一个候选相同，就把属于那个候选的点数统计加1，

　　　　如果与所有的候选都不相同

　　　　　　先看当前的候选是否选满了，选了k-1个，就是满;否则就是没有选满

　　　　　　如果不满，把arr[i]作为一个新的候选，属于它的点数初始化为1

　　　　　　如果已满，说明此时发现了k个不同的数，arr[i]就是第k个。此时把每一个候选各自的点数全部减1，表示每个候选“付出”一个自己的点数。如果某些候选的点数在减一之后等于0，则还需要把这些候选cond[...]删除，候选又变为不满的状态。

 

在上述过程结束后，还需要再遍历一次，验证被选出来的所有候选有哪些出现次数真的大于N/K，符合条件的候选就打印。

229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

 

代码在这里,

但是在leetcode上提交由runtime error，我没有发现什么问题。

1 class A{ 2 public: 3   vector
     
       majorityElement(vector
      
       & nums) { 4         int n = nums.size(); 5         unordered_map
       
         candTimes; 6         vector
        
          re; 7         for(int i = 0;i
         
          ::iterator mit = candTimes.begin();15                         mit!=candTimes.end();mit++){16                         if(mit->second==1){17                             candTimes.erase(mit);18                         }else{19                             mit->second--;20                         }21                     }22                 }23            }///if-else24         }///for25 26         ///verify the solution27         for(unordered_map
          
           ::iterator mit = candTimes.begin();28 mit!=candTimes.end();mit++){29 mit->second = 0;30 }31 32 for(int i = 0;i
           
            ::iterator mit = candTimes.begin();40 mit!=candTimes.end();mit++){41 if(mit->second>(n/3)){42 re.push_back(mit->first);43 }44 }45 return re;46 } 47 };