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.

思路1：每找出两个不同的element，则成对删除。最终剩下的一定就是所求的。

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

class Solution {public:    int majorityElement(vector
     
      & nums) {        int nTimes = 0;        int candidate = 0;        for(int i = 0; i < nums.size(); i ++)        {            if(nTimes == 0)            {                candidate = nums[i];                nTimes = 1;            }            else            {                if(candidate == nums[i])                    nTimes ++;                else                    nTimes --;            }        }        return candidate;    }};
     

思路2：随机挑选一个元素，检查是否是多数元素。时间复杂度：Average：O(n)。期望查找次数 <2

class Solution {public:    int majorityElement(vector
     
      & nums) {         int count = 0;                   for(;;) {             if(nums.size() == 1)                 return nums[0];             else    {                 int i = rand() % (nums.size() - 1);                 for(int j = 0; j < nums.size(); j++) {                     if(nums[j] == nums[i])                         count++;                 }                 if(count > (nums.size() / 2))                     return nums[i];                 else    {                     count = 0;                     continue;                 }             }         }    }};
     

思路3：

class Solution {public:    int majorityElement(vector
     
      & nums) {        std::map
      
        im;    for (int i = 0; i < nums.size(); ++i){        map
       
        ::iterator it = im.find(nums[i]);        if (it == im.end()) {            im[nums[i]] = 1;        } else {            im[nums[i]]++;        }        if (im[nums[i]] > nums.size()/2) {            return nums[i];        }    }    return 0;    }};
       
      
     

思路4：

class Solution {public:    int majorityElement(vector
     
      & nums) {        int majority;    int cnt = 0;    for(int i=0; i
      
       = nums.size()/2+1) return majority;        }    }    return majority;    }};