在数组中寻找出现次数大于N/K的数

给定一个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，我没有发现什么问题。

 class A{

 public:

   vector<int> majorityElement(vector<int>& nums) {

         int n = nums.size();

         unordered_map<int,int> candTimes;

         vector<int> re;

         for(int i = ;i<n;i++){

            if(candTimes.find(nums[i])!=candTimes.end()){

                 candTimes[nums[i]]++;

            }else{

                 if(candTimes.size()<){

                     candTimes[nums[i]]++;

                 }else if(candTimes.size()==){

                     for(unordered_map<int,int>::iterator mit = candTimes.begin();

                         mit!=candTimes.end();mit++){

                         if(mit->second==){

                             candTimes.erase(mit);

                         }else{

                             mit->second--;

                         }

                     }

                 }

            }///if-else

         }///for

         ///verify the solution

         for(unordered_map<int,int>::iterator mit = candTimes.begin();

             mit!=candTimes.end();mit++){

             mit->second = ;

         }

         for(int i = ;i<n;i++){

             if(candTimes.find(nums[i])!=candTimes.end()){

                 candTimes[nums[i]]++;

             }

         }

         for(unordered_map<int,int>::iterator mit = candTimes.begin();

             mit!=candTimes.end();mit++){

             if(mit->second>(n/)){

                 re.push_back(mit->first);

             }

         }

         return re;

     }

 };

巴特西

在数组中寻找出现次数大于N/K的数

最新文章

热门文章