问题

找出数组中的多数元素（超过一半）

算法

直接遍历计数即可，可以用一个变量cnt来记录下多数元素的出现次数

复杂度

时间：O(N)
空间：O(1)

代码

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