算法：寻找多数元素

题目

  已知一个数组中存在一个众数，请找出这个众数。众数是指一个数组中的数出现的次数超过数组长度的一半。

思路

  看到这道题的第一眼，想到的方法是，遍历数组，给每个数计数，然后找到数量最多的数返回。这个算法的时间和空间复杂度都是O(n)。没想到还有更优秀的做法。这个方法就是摩尔投票法。摩尔投票法的思路就是，遍历数组，也是给数计数，不过有点不一样。

  首先任选一个候选人，计数为1，一般都是从第一个数开始。遇到相同的数就加1，遇到不同的就减1，如果计数为0，则把当前的数作为候选人，计数为1。重复这个过程到数组的最后。候选人就是答案。时间复杂度为O(n),空间复杂度为O(1)

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 1;
        int maj = nums[0];
        for(int i = 1;i < nums.size();i++) {
            if (nums[i] == maj) {
                count++;
            }
            else {
                if (count == 0) {
                    maj = nums[i];
                    count++;
                }
                else {
                    count--;
                }
            }
        }
        return maj;
    }
};