题解 | #草原上优势牛种#

考察知识点：数组、摩尔投票算法

绝对众数：绝对众数就是一个在某个序列中个数超过序列中数的总个数的1/2的数。

题目分析：

题目中优势群种满足绝对众数的要求。可以使用摩尔投票算法，能很好的降低空间复杂度。

摩尔投票算法很好的利用了“众数的个数超过原序列中数的总数的一半”的性质，企图用众数与其他不是众数的任何数抵消掉：每次将一个众数和非众数同时删除的话，最终能剩下众数。

首先我们假设第一个数是众数，记录众数出现的次数并向后遍历，当遇到相同的数时，就记录该数又出现了一次。当遇到不同的数时，可能这个数是众数，也可能不是。我们还是保持之前的假设，但是要用记录的众数的次数减1，来抵消掉这个遍历到的数。

当记录的众数出现的次数为0时，说明可能不是众数，起码在遍历过的数（m个）中它没有出现1 / 2 * m次。此时我们就选择当下遍历到的数为众数。不必担心我们错误假设了众数，因为众数是非常多的，相抵消后得到的数就是众数。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int majority_cow(vector<int>& nums) {
        // write code here
        int size = nums.size();
        int res;
        int cnt = 0;
        for (int i = 0; i < size; i++) {
            if (cnt == 0) {
                res = nums[i];
                cnt++;
            } else if (res != nums[i]) {
                cnt--;
            } else {
                cnt++;
            }
        }
        return res;
    }
};