编程题-多数元素

题目：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解法一（哈希表）：

使用哈希表可以快速统计出每个元素出现的次数，使用哈希映射来存储每个元素以及出现的次数。哈希表中“键”表示出现的元素，而“值”表示元素出现的次数。

使用一个循环遍历数组num并将数组中每个元素加入哈希表中，在这之后，遍历哈希表中所有的键值对，返回值最大的键。如下为代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //定义哈希表counts
        unordered_map<int, int> counts;
        // majority表示多数的元素，cnt表示多数元素的数量
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

笔者小记：counts哈希表中可以直接使用counts[num]++，即在哈希表添加元素时默认键对应的值为0，再哈希表内之前没有的键中调用公式counts[num]++默认值为1，不用再判断是否为空导致可能会发生的报错现象。

解法二（摩尔投票算法）：

由题可知，如果我们把众数记为+1，把其他数记为-1，将它们全部加起来，显然和大于0，从结果本身我们可以看出众数比其他数多。因此我们假设第一个元素为众数+1，若后续不是这个元素则-1，是这个元素则继续+1，直至为0后又遇到不是这个元素的数，此时设置这个数为假设的众数，当遍历完最后一个元素时，剩下的那个元素肯定是这个最多的数，本思想实则上是分治思想，如下代码为：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
};