问题描述
同学X喜欢玩微信红包，然后年后统计自己的红包收入，发现有这样一个问题：
一共收了N个红包，然后其中金额为k的红包出现次数大于N/2;让你写程序求解k值（要求程序足够优化）
问题分析：
这个题目明确告诉我们，所求为出现次数大于一半的，也就是最多的那个份额。也就是数学里众数这个概念了，且这个题目中更明确规定了，这个众数是大于总数的一半的。
在这个明确的条件之后，更是要求我们的程序更高效，优化方案。
方案与思路
①因为这是个有序问题，那么实现方案可以是
排序，然后统计比较计算出出现次数最多的一个
//伪代码：
void test(int *arr,int N)
{
//1排序
//2二次遍历统计，找出最大
}
②对一进行优化，在排序同时记录每个数字第一次出现在排序中的下标，然后通过区间宽度进行确立
void test(int *arr,int N)
{
//1排序，记录首次出现下标
//1111,2222,33333,44444444444,55
//0 4 8 13...
//注：这个下标确立可以通过几个指针标记
//2区间宽度确立：计算宽度，找到宽度最宽的区间，然后对指针解引用得到值
}
③改进算法
void Find(int *a, size_t size) { int count = 0; int tmp; tmp = a[0]; count++; for (int i = 1; i < size; ++i) { if (a[i] == tmp) { count++; } else { count--; } if (count == 0) { tmp = a[i]; count = 1; } } cout << tmp; } void test() { int arr1[] = { 1, 2, 3, 5, 1, 2, 1, 1, 1, 5, 7, 1, 1 }; Find(arr1, 13); }
void Find(int *a, size_t size){int count = 0;int tmp;tmp = a[0];count++;for (int i = 1; i < size; ++i){if (a[i] == tmp){count++;}else{count--;}if (count == 0){tmp = a[i];count = 1;}}cout << tmp;}
void test(){int arr1[] = { 1, 2, 3, 5, 1, 2, 1, 1, 1, 5, 7, 1, 1 };Find(arr1, 13);}