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.

 

Analyse: map. 

Runtime: 40ms.

1 class Solution { 2 public: 3     vector
     
       majorityElement(vector
      
       & nums) { 4         int n = nums.size(); 5         map
       
         m; 6         vector
        
          result; 7          8         for(int i = 0; i < n; i++){ 9             if(m.find(nums[i]) != m.end())10                 m[nums[i]]++;11             else12                 m[nums[i]] = 1;13         }14         15         for(map
         
          ::iterator ite = m.begin();  ite != m.end(); ite++){16             if(ite->second > n / 3)17                 result.push_back(ite->first);18         }19         return result;20     }21 };