【LeetCode热题100】【技巧】多数元素

题目链接：169. 多数元素 - 力扣（LeetCode）

其实就是找众数，可以用哈希表记录每个元素的出现次数，然后返回最多的，或者排序一下返回中间位置的数

但是如果要O(n)的时间复杂度和O(1)的空间复杂度，可以用同归于尽消杀法，如果数组里面这个数的数量超过了一半，那么其他数和他同归于尽后最后还是剩下他

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