题目概述
解题思路
方法1
进行排序,排序后,超过一半次数的数字一定会出现数组的最中间的位置上
方法2
利用快排的思想,单次排序,会将数组分成两个区间
通过判断所分区间的中间元素是否为数组的中间值
来进行逐次划分求解
这里和快排很相似,就没有实现
时间复杂度为O(N)
方法3
巧妙思路
用两个变量,一个保存当前记录的数字,一个保存次数(初始化为0)
遍历一遍数组
如果数字与当前数保持相同,则次数加1
否则,次数减1
若次数减为0,则保存下一个位置的数字
时间复杂度O(N)
代码实现
方法1
//方法1:排序后取中间值
//直接插入排序的思想
//分成两个数组
//第一个数组是有序的,第二个是无序的
//开始的时候,只有第一个数在第一个数组
//升序
void InsertSort(int* arr, size_t n)
{
for (int i = 1; i < n; ++i)
{
int j = i - 1;
int tmp = arr[i];
for (; j >= 0; --j)
{
//如果tmp比该位置大
if (tmp > arr[j])
break;
arr[j + 1] = arr[j];
}
arr[j+1] = tmp;
}
}
int MoreThanHalf1(int* arr, size_t n)
{
InsertSort(arr, n);
int midIndex = n >> 1;
return arr[midIndex];
}
该算法的时间复杂度为O(N^2)
可以用其他排序,最快为O(N*logN)
方法3
//方法3
//用快排,找中间的数
//方法3
//用技巧
pair<bool,int> MoreThanHalf3(int* arr, size_t n)
{
int num = arr[0];
int count = 1;
for (size_t i = 1; i < n; ++i)
{
if (num == arr[i])
count++;
else
count--;
if (count == 0)
{
if (i >= n - 1)
return make_pair(false,0);
num = arr[i + 1];
}
}
return make_pair(true, num);
}
方法3中,注意判断传入数组有误的情况
用pair结构体,第一个元素表示数组是否符合题目要求
第二个元素表示最后返回的超过一半的数字
当然,如果第一个元素为FALSE,则第二个元素就不用关心了
转载请注明原文地址: https://ju.6miu.com/read-500111.html