数组中出现次数超过一半的数字

关键词：摩尔投票法（打擂台）

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例 1：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

解法

解法一：

思路：

• 该数字的数量比其他所有数字数量总和多

算法流程：

1. 假设第一个数字是目标值，给它计一票；
2. 遍历数组，遇到相同的元素则计票，否则减少票数；
3. 当票数减少为零时，令下一个数字为暂定目标值。

代码：

int majorityElement(vector<int>& nums) {
    int n = 1;
    int res = nums[0];
    for(int i = 1; i < nums.size(); i++){
        if(res == nums[i]) n++;
        else n--;
        if(n == 0){
            if(i == nums.size() - 1) return 0;
            i++;
            res = nums[i];
            n = 1;
        }
    }
    return res;
}

知识点

1. 摩尔投票法（打擂台）