题目概述

解题思路

方法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，则第二个元素就不用关心了