算法与数据结构（多数元素）

题目

思路

方法一：哈希表

因为要求出现次数最多的元素，所以我们可以使用哈希映射存储每个元素及其出现的次数。每次记录出现的次数若比最大次数大，则替换。

方法二：摩尔算法

摩尔的核心算法就是对抗，因为存在次数多于一半的数，不同的元素相互抵消，那么剩下的一定就是出现次数最多的那个数。

比如，假设数组是[3,2,3]。初始时，candidate是-1，count是0。第一个元素是3，这时候num不等于candidate（-1），所以执行else if的条件。count减1的话，这时候count是-1，是否满足小于0？是的。于是将candidate设为3，count设为1。接下来是第二个元素2。这时候num不等于3，所以count减1，变成0。这时候count不满足小于0，所以不做任何改变。第三个元素是3，等于candidate，所以count加1，变成2。最后返回3。

这个算法的正确性在于，当存在多数元素时，即使中间阶段被其他元素暂时替代，最终剩下的candidate还是多数元素。因为多数元素的个数超过一半，所以无论如何抵消，最后剩下的肯定是多数元素。

这个算法的核心就是是，每次遇到不同的元素，就减少count，当count减到负的时候，更换候选者。这其实相当于在每一步中，当前的候选者和其他元素进行对抗，如果当前候选者不足以支撑（count被抵消到负），就换新的候选者。这样最终剩下的候选者就是多数元素。

代码

1.哈希表

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int> Hashmap;int value=0,freq=0;for(int i=0;i<nums.size();i++){Hashmap[nums[i]]++;if(Hashmap[nums[i]] > freq){value = nums[i];freq = Hashmap[nums[i]];}}return value;}
};

2.摩尔算法

class Solution {
public://摩尔算法int majorityElement(vector<int>& nums) {int candidate=-1,count=0;for(int i=0;i<nums.size();i++){if(nums[i]==candidate){count++;}else if(--count < 0){candidate = nums[i];count = 1;}}return candidate;}
};