如何找到数组中出现次数超过数组长度一半的数

如何找到数组中出现次数超过数组长度一半的数

#include
using namespace std;



int Partition(int *A,int low,int high)
{
int pivotkey=A[low];
while (low{
while (low=pivotkey)
{
high--;
}
A[low]=A[high];
while (low{
low++;
}
A[high]=A[low];
}
A[low]=pivotkey;
return low;
}

bool confirmNum(int *array,int number,int len)
{
int time=0,i;
for (i=0;i{
if (array[i]==number)
{
time++;
}
}
if (time*2>len)
{
return true;
}
else
return false;
}

void MoreThanHalfArray(int *array,int len)
{
int middle=len/2;
int index,start=0,end=len-1;
index=Partition(array,start,end);
while (index!=middle)
{
if (index>middle)
{
end=index-1;
index=Partition(array,start,end);
}
else
{
start=index+1;
index=Partition(array,start,end);
}
}
int result=array[middle];
if (confirmNum(array,result,len))
{
cout<}
else
cout<}



void MoreThanHalf(int *array,int len)
{
int i;
int result,time=0;
for (i=0;i{
if (time==0)
{
result=array[i];
time=1;
}
else if (array[i]==result)
{
time++;
}
else
time--;
}
if (confirmNum(array,result,len))
{
cout<}
else
cout<}

int main()
{
int array[]={1,2,3,2,2,2,5,4,2};
MoreThanHalfArray(array,9);
MoreThanHalf(array,9);
return 0;
}
这两种实现都能在O（n）时间内完成，要优于先排序然后找数组元素的方法。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息