标题描绘
数组中有一个数字呈现的次数超越数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。因为数字2在数组中呈现了5次，超越数组长度的一半，因而输出2。假如不存在则输出0。
解法一：map容器计算每个数字次数。
#include
#include
#include
#include
using namespace std;
class Solution {
public:
int MoreThanHalfNum_Solution(vectornumbers) {
int length = numbers.size();
if(length == 0)
return 0;
map
for(int i = 0; i < length; i++)
m[numbers[i]]++;
length >>=1;
for(map
{
if(it -> second > length)
{
return it->first;
break;
}
}
return 0;
}
};
解法二：时刻复杂度能够到达O(N)
因为要找的数字的呈现次数大于数组长度的一半，这个数字呈现的次数比其他数字呈现的次数总和还要多， 所以能够遍历数组保存两个值，temp numj_temp，即数组中的数字和次数，初始为numbers[0], 1.
当扫描到的数字和temp不同的时分，则num_temp-- 不然自增。
假如此刻num_temp==0，则更新temp为当时的数字，且把num_temp重置为1
要找的数字肯定是最终一次把num_temp设定为1（或许大于1）的数字
class Solution {
public:
int MoreThanHalfNum_Solution(vectornumbers) {
int length = numbers.size();
if(!length)
return 0;
int temp = numbers[0];
int num_temp = 1;
for(int i = 1; i < length; i++)
{
if(num_temp == 0)
{
temp = numbers[i];//改动此刻次数最多的数字
num_temp = 1;
}
else if(numbers[i] == temp)
num_temp++;
else
num_temp--;
}
if(check(numbers, temp, length))//判别是不是真的呈现次数超越数组长度的一半
return temp;
else
return 0;
}
bool check(vectornumbers, int num, int length)
{
int ans = 0;
for(int i = 0; i < length; i++)
if(numbers[i] == num)
ans++;
if(ans *2 <= length)
return false;
return true;
}
};
A8站源码交易平台
