力扣对应题目链接：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++;
else
times--;
}
int cnt=0;
for(int i=0; i<n; i++)
{
if(nums[i]==target)
cnt++;
}
return cnt>n/2?target:0;
}
};
