本文主要是介绍剑指offer之数组中次数超过一半的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入长度为9的数字{1，2 ，3，2，2，2，5，4，2}，由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
分析：
如果把这个数组排序，那么排序后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字，即长度为n的数组中的n/2大的数字。
代码：
int MoreThanHalfNum(int * numbers，int length)
{
if(CheckInvalidArray(numbers，length))
return 0;
int middle = length >> 1;
int start = 0;
int end = length -1 ;
int index = Partition(numbers，length，start，end); //Partition 是快速排序算法
/* 如果选中数字的下标刚好是n/2，那么这个数字就是数组的中位数；如果它的下标小于n/2，那么中位数就位于它的右边；如果下标大于n/2，那么中位数就位于它的左边。*/
while(index != middle)
{
if(index > middle)
{
end = index -1;
index = Partition(numbers，length，start，end);
}
else
{
start = index + 1;
index = Partition(numbers，length，start，end);
}
}
int result = numbers[middle]; //找到中间位数
if(!CheckMoreThanHalf(numbers，length，result)) //用来确定找到的数字占数组的一半以上
result = 0;
return result;
}
本题考查对时间复杂度的理解，时间复杂度为o(n)。
这篇关于剑指offer之数组中次数超过一半的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
