时间复杂度O(n)
    空间复杂度O(1)

    1. class Solution {
    2. public:
    3.     // 摩尔投票法
    4.     // 因为多数元素在数组中出现的次数大于一半
    5.     // 所以这个元素出现的次数是大于其它所有元素出现次数之和的
    6.     // 也就是说如果每个多数元素和其余元素两两抵消，最后肯定会剩余至少一个多数元素
    7.     // 不同的数两两抵消，最后剩下的一定会是那个多数元素
    8.     int majorityElement(vector<int>& nums) {
    9.         // 在一开始我们将当前元素初始化为nums[0]，记录它的票数为1
    10.         int cur = nums[0], cnt = 1;
    11.         // 如果后面遇到与他相同的数，票数+1，否则票数-1
    12.         for (int i = 1; i < nums.size(); i++) {
    13.             if (nums[i] == cur) cnt++;
    14.             // 当票数为0时，更换候选人，并将票数重置为1
    15.             else if (cnt-- == 0) {
    16.                 cur = nums[i];
    17.                 cnt = 1;
    18.             }
    19.         }
    20.         // 数组遍历完后，剩下的候选人就是数组的多数元素
    21.         return cur;
    22.     }
    23. };