寻找众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]

输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]

输出：2

1.很简单的排序，因为众数大于总长度的1/2，故排序后的中位数必定是众数。(刚开始还全都寻找了一遍)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
        sort(nums.begin(), nums.end());
        int num = 0;
        int major = nums[0];
        int max = 0;
        //for(int i = 0; i < nums.size(); i++){}
        int i = 1;
   /*     while(i < nums.size()){
            if(nums[i] == nums[i-1]){
                num++;                 
            } else{
                num = 1;                                
            }
            if(num > nums.size()/2){
                max = max;
                major = nums[i];
                break;
            }
            i++;
        }*/
        return nums[nums.size()/2];        
        return major;        
    }
};      

2. 摩尔计数法

1.首先确定一个计数器以及candidate，

如果数组中存在和目标值相同，则计数器加一，否则计数器减一。当计数器减为0时，则换一个candidate。

计数器减为0表示该目标值的相同值与不同值已经相互抵消了，而众数由于大于1/2的长度，必然能够使得最后的计数器不为0.

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