Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

 Solution 1: 使用map计数

1 class Solution { 2 public: 3     int majorityElement(vector
     
      & nums) {　　　　//runtime:32ms 4         map
      
        nums_count; 5         vector
       
        ::iterator iter=nums.begin(); 6          7         while(iter!=nums.end()){ 8             ++nums_count[*iter]; 9             iter++;10         }11         12         int n=nums.size();13         14         map
        
         ::iterator ite=nums_count.begin();15         //int max=ite->second;16         while(ite!=nums_count.end()){17             if(ite->second>n/2){18                 return ite->first;19             }20             ite++;21         }22     }23 };
        
       
      
     

Solution 2: 每找出两个不同的element就成对删除，最后可能剩两个元素或一个元素，必定都是所求

 

1 class Solution { 2 public: 3     int majorityElement(vector
     
      & nums) {    //runtime: 20ms 4         int count=0; 5         int ret; 6         for(int i=0;i
     

扩展到⌊ n/k ⌋的情况，每k个不同的element进行成对删除