数组中出现次数超过一半的数字
    题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
    图片.png

    思路：记录摩尔投票法的思路。每次当vote = 0时假设当前的num就是目标数字，并基于以下两个invariant：

    • 若目标数字vote++，其他数字vote—，则最后vote必然>0
    • 若前n个数的vote = 0，则剩余部分数字的vote依然>0，也就是说目标数字不会发生变化

    简单来说，就是目标数字与其他数字一一抵消，最后剩下的必然还是目标数字。

    参考代码：

    1. class Solution {
    2. public:
    3.     int majorityElement(vector<int>& nums) {
    4.         int vote = 0;
    5.         int num;
    6.         for (int i = 0; i < nums.size(); ++i) {
    7.             if (vote == 0) {
    8.                 num = nums[i];
    9.                 ++vote;
    10.                 continue;
    11.             }
    12.             if (nums[i] == num) {
    13.                 ++vote;
    14.             }
    15.             else {
    16.                 --vote;
    17.             }
    18.         }
    19.         return num;
    20.     }
    21. };