169. Majority Element

题目：

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

Follow-up: Could you solve the problem in linear time and in O(1) space?

思路：

要求O(1)复杂度，这里介绍一个投票算法。用一个cur表示当前数字，用count表示当前数字"获取的票数"。遍历数组nums，遍历值为n，如果如果cur和n相同，那么count增加一；如果不同，count减少一，但是如果count小于0了，count更新为1并且cur更新为n。解析下面答复有个理解很好，引用一下，“如果碰到和当前数字(即这里的cur)不同的数，那么获取的票数(count)减一，因为不是cur的话肯定是反对票；如果相同的话获取的票数(count)加一因为当前数字(cur)会自己投给自己”。这里为什么count < 0 才更新而不是等于0就更新呢？假设[7,7,3,4]，到第二个7的时候，cur=7，count=2，虽然到4的时候count为0，但是7依然是众数，因此要count小于0时，cur才会“换届”。

代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cur = -1, count = 0;
        for (auto n : nums) {
            if (n == cur)
                count++;
            else {
                count--;
                if (count < 0 ){
                    count = 1;
                    cur = n;
                }
            }
        }
        return cur;
    }
};