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.

Credits:

Special thanks to for adding this problem and creating all test cases.

 

to see which companies asked this question

这道题我还是用map做的，对于某个关键字有这种计数类的性质的题目用map真的很好用，关键点还是记得map里面的元素是pair，我们需要（*i）.first，最后是32ms，还不错吧

一次提交就accepted还是非常开心的。

1 class Solution { 2 public: 3     int majorityElement(vector
      
       & nums) { 4         map
       
         eleTimes; 5         int temp=0,count=0,sta=0; 6         sta=nums.size()/2; 7         if(sta==0) return nums[0]; 8         for(auto i=nums.begin();i!=nums.end();i++){ 9             temp=(*i);10             ++eleTimes[temp];11         }12         for(auto j=eleTimes.begin();j!=eleTimes.end();j++){13             count=(*j).second;14             if(count>sta) return (*j).first;15         }    16         }17         18     19 };
       
      

---

后来还看了一种比较简单的思想，但是理解起来比较困难

[C++ Solution] [O(n) computation/O(1) space] The problem can be extended to ⌊n/k⌋ situation

Find k different element, and "remove" them as a group, the remaining element must be the element that appears more than ⌊n/k⌋ times. (Detailed explanation is given in comment)

In this problem, k equals to 2.

Thus we "remove" each pair of 2 different elements, and the remaining element that do not have its counterpart is the desired element. 

 

就是成k对去“删除”不相同的元素：

例如5个元素的时候，5,3,4,3,3这种情况下，5，3会被删除，4,3会被删除，最后就剩下3；

5,3,3,4,3:5,3会被删除，3,4会被删除，留下3

5,3,3,3,4：5,3会被删除，candidate是第二个3，因为接下来的元素还是3,于是Ntimes变成了2，即使后面的4与其不相同，Ntimes没有被减至0，于是，被返回。

1 class Solution { 2 public: 3     int majorityElement(vector
      
        &num) { 4         int nTimes = 0; 5         int candidate = 0; 6         for(int i = 0; i < num.size(); i ++) 7         { 8             if(nTimes == 0) 9             {10                 candidate = num[i];11                 nTimes = 1;12             }13             else14             {15                 if(candidate == num[i])16                     nTimes ++;17                 else18                     nTimes --;19             }20         }21         return candidate;22     }23 };