数组中有一个数字出现的次数超过了,
在BM51数组中出现超过一半时间的数字
知识点哈希数组
描述一个长度为n的数组，数组中有一个数字出现的长度超过数组长度的一半。请找到这个号码。例如，输入一个长度为9的数组[1，2，3，2，2，2，5，4，2]。因为数字2在数组中出现了五次，超过数组长度的一半，所以输出2。
数据范围：数组中元素的值要求：空间复杂度：时间复杂度
描述：确保数组输入不为空，并且有解决方案。
示例1输入：
[1，2，3，2，2，2，5，4，2]复制返回值：
2份副本
2示例输入：
[3，3，3，3，2，2，2]复制返回值：
3份
3示例输入：
[1]复制返回值：
一个
解决哈希问题的时间复杂度：O(n)
空间复杂度：O(n)
int MoreThanHalfNum_Solution(向量整数)
{
unordered_map int，int mp
for(常量整数值：数字)
MP[val]；
for(常量整数值：数字)
{
if (mp[val] numbers.size()/2)
返回val
}
返回0；
}排序法可以先对数组进行排序，然后可能的模式一定是在数组中间，再进行判断。
int MoreThanHalfNum_Solution(向量整数)
{
sort(numbers.begin()、numbers . end())；
int cond=numbers[numbers . size()/2]；
int CNT=0；
for (const int k : numbers)
{
if (cond==k)
cnt
}
if (cnt numbers.size()/2)
返回cond
返回0；
}候选方法被添加到数组中。如果有模式，那么模式必须大于数组长度的一半。
想法是：如果两个数不相等，就会被淘汰。最坏的情况下，每次会淘汰一个模态和一个非模态。如果有模式，剩下的最后一个数字一定是模式。
具体做法：
初始化：候选人cond=-1，候选人的投票次数cnt=0遍历数组。如果cnt=0，则表示没有候选项，然后选择当前数字作为候选项。否则，如果cnt 0，说明有候选。如果当前数值=cond，则cnt。否则，- cnt直到遍历完数组。最后，检查cond是否占多数。
代码如下：
int MoreThanHalfNum_Solution(向量整数)
{
int count=0；
int target=0；
for(int I=0；I numbers . size()；我)
{
if (count==0)
{
数数；
target=numbers[I]；
}
其他
{
if(数字[i]==目标)
{
数数；
}
其他
{
count-；
}
}
}
返回目标；
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。