数组中出现次数超过一半的数字一类题模板

1.数组中出现次数超过一半的数字

对应链接：

力扣

题目描述:

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

输出: 2

限制：

1 ⌊ n/2 ⌋的一长串由相同元素构成的连续子数组那么中间元素一定是出现次数大于n/2的元素举个例子：

无论是1 1 1 2 3，0 1 1 1 2还是-1 0 1 1 1，数组中间的元素总是“多数元素”，毕竟它长度> ⌊ n/2 ⌋。

对应代码：

class Solution {
public:int majorityElement(vector& nums) {sort(nums.begin(),nums.end());//排序return nums[nums.size()/2];}
};

但是这样的时间复制度是0（N*logN)

方法二：hash表

直接遍历整个 数组 ，将每一个数字（num）与它出现的次数（count）存放在 哈希表 中，同时判断该数字出现次数是否是最大的，动态更新 ，最后输出 。

对应动图：

对应代码：

class Solution {
public:int majorityElement(vector& nums) {int maxCount=0;int maxNum=0;unordered_maphash;for(auto x:nums){hash[x]++;if(hash[x]>maxCount){//更新出现次数最多的数字maxCount=hash[x];maxNum=x;}}return maxNum;//返回结果}
};

方法三：摩尔庄园投票

对应思想：

我们遍历投票数组，将当前票数最多的候选人与其获得的（抵消后）票数分别存储在 major 与 count 中。

当我们遍历下一个选票时，判断当前 count 是否为零：

若 count == 0，代表当前 major 空缺，直接将当前候选人赋值给 major，并令 count++

若 count != 0，代表当前 major 的票数未被完全抵消，因此令 count--，即使用当前候选人的票数抵消 major 的票数

以[2,2,1,3,1,2,2]为例。

遍历数组第一个元素2时，因major空缺，所以赋值major = 2，且票数count = 1：

我们发现第二个元素依旧是「候选人」2，与major相同，因此将票数加一：

第三个元素是1，与major不同，因此发生「对抗」，将当前major的票数冲抵掉 1 票：

第四个元素是3，又与major不同，因此产生「对抗」，票数继续冲抵：

当遍历到第五个元素1时，我们发现当前count已经归0，说明major位置空缺，因此我们令major = 1，且count = 1：

第六个元素是2，与major不同，因此进行票数抵消，元素1刚上位又要下台了：

此时count又归零了，因此当遍历到最后一个元素2时，令major = 2，票数count = 1：

遍历结束求出多数元素为2

对应代码：

class Solution {
public:int majorityElement(vector& nums) {int major = 0;int count = 0;for(auto x:nums){if(count==0){major=x;}if(x==major){count++;//相同则++}else{count--;//不相同则--；}}return major;}
};

求众数ll

对应链接：

力扣

题目描述：

给定一个大小为n的整数数组，找出其中所有出现超过⌊ n/3 ⌋次的元素。

示例1：

输入：[3,2,3]

输出：[3]

示例 2：

输入：nums = [1]

输出：[1]

示例 3：

输入：[1,1,1,3,3,2,2,2]

输出：[1,2]

提示：