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

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

示例 1：

**输入：**nums = [3,2,3]
**输出：**3

示例 2：

**输入：**nums = [2,2,1,1,1,2,2]
**输出：**2

提示：

n == nums.length

1 <= n <= 5 * 10(4)

-10(9) <= nums[i] <= 10(9)

输入保证数组中一定有一个多数元素。

**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

投票法，因为答案只有一个，所以数组也可以分为两类

两类之间可以相互抵消，最后剩的一类就是答案

所以我们可以在遍历过程中记录 当前两类的比较结果 和 目前胜出的是哪一类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int> &nums) {
        int num = 0; // 投票结果
        int index;
        for (int i = 0; i < nums.size(); i++) {
            if (num == 0) // 0票，当前遍历的就是当前胜出的
                index = i;
            if (nums[i] == nums[index])
                num++;
            else
                num--;
        }
        return nums[index];
    }
};