【一刷《剑指Offer》】面试题 29：数组中出现次数超过一半的数字

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

牛客对应题目链接：数组中出现次数超过一半的数字_牛客题霸_牛客网 (nowcoder.com)

核心考点 ： 数组使用，简单算法的设计。

---

一、《剑指Offer》对应内容

---

二、分析题目

这里找到的题目链接所对应的数据都满足数组是非空的，并且给定的数组总是存在多数元素。所以下面就不再另外判断了。

• 思路一：定义 map/unordered_map，使用 <int, int> 的映射关系，最后统计每个字符出现的次数。
• 思路二：排序，出现次数最多的数字一定在中间位置，然后检测中间出现的数字出现的次数是否符合要求。
• 思路三：目标条件：目标数据超过数组长度的一半。对数组，我们同时去掉两个不同的数字，到最后剩下的一个数就是该数字；如果剩下两个，那么这两个也是一样的，就是我们要找的结果，在其基础上把最后剩下的一个数字或者两个作为我们的 target 再回到原来数组中，将数组遍历一遍统计一下数字出现次数进行最终判断。

---

三、代码（C++）

1、哈希（unordered_map）

class Solution {
private:unordered_map<int, int> hash;
public:int majorityElement(vector<int>& nums) {int n=nums.size();int half=n/2;for(int x:nums){hash[x]++;if(hash[x]>half)return x;}return 0;}
};

---

2、排序

class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());int n=nums.size();return nums[n/2];}
};//如果题目没有说明总是存在多数元素
class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());int n=nums.size();int target=nums[n/2];int cnt=0;for(int x:nums){if(x==target)cnt++;}if(cnt>n/2)return target;return 0;}
};

---

3、利用特殊性寻找目标值

class Solution {
public:int majorityElement(vector<int>& nums) {int n=nums.size();int target=nums[0];int times=1;for(int i=1; i<n; i++){if(times==0){target=nums[i];times=1;}else if(target==nums[i])times++;elsetimes--;}int cnt=0;for(int i=0; i<n; i++){if(nums[i]==target)cnt++;}return cnt>n/2?target:0;}
};