名企笔试：腾讯招聘笔试（微信红包）
题目描述
春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。
若没有金额超过总数的一半，返回0。
测试样例：
[1，2，3，2，2]，5
返回：
2
分析：
找到出现一般的超过红包，就是找到超过一半的数，若没有超过一半的数就返回0。
想法一、排序，返回中位数，然后计算中位数的个数，如果超过一半就返回，否则返回0。时间复杂度是O(nlog(n))+O(n)：排序+遍历一遍确定是否是超过一半的数。空间复杂度O(1)。
想法二、使用hash函数，计算每一个数出现的次数，然后便利hash表，返回个数超过一半的数。时间复杂度O(n)；分别是计数+遍历hash表+验证。空间复杂度O(n)。
想法三、如果一个数出现次数超过一半，我们任意去掉两个不相同的数，剩下的数组中，仍然有一个数出现的次数是剩下数组的一半。假设出现一半的数是a，我们每次去掉两个不相同的数b和c。如果b！=a且c！=a,那么剩下的数然后是a超过剩余数组的一半。假如a=b，我们去掉两个数，count[a] = k > n/2；去电b和c后数组长度n-2；count(a)=k-1 > n/2 – 1 = (n-2)/2。
我们编程的时候是否每次都要删除两个不同的数呢？删除数组中的数的时间复杂度是O(n)。时间 复杂度更高。其实我们可以用计数来使用这个思想。第一至k=1,标记a=A[1]；（A是一个数组，长度是n）。遍历一遍数组，如果有A[i] = a; k+=1;
else: k -=1;当出现k=0时证明前一个候选的值不是超过一半的数，因此另k=1；a = A[i]
直到最后结束，得到a。确定a的个数是否大于一半即可。时间复杂度O(n)；计数+验证。空间复杂度O(1)。
Code:
#include<iostream>#include<stdio.h>#include<map>#include<algorithm>using namespace std;//这里的测试数据默认是a数组int a[] = {1,2,3,2,2};//int a[] = {1,2,3,4,5};bool isThisDigit(int res,int n){int k = 0;for(int i=0;i<n;i++){if(res == a[i]) k++;}return k > n/2;}//排序+验证int test1(int n){sort(a,a+n);int result = a[n/2];//验证if(isThisDigit(result,n)) return result;else return 0; }int test2(int n){map<int,int> cnt;for(int i=0;i<n;i++){cnt[a[i]] ++;}map<int,int>::iterator it;int result = 0,k = 0;for(it = cnt.begin();it!=cnt.end();++it){if(it->second > k){result = it -> first;k = it->second;}}if(isThisDigit(result,n)) return result;else return 0;}int test3(int n){int result=a[0],k=1;for(int i=1;i<n;i++){if(a[i] == result) k++;else k--;if(k==0){//更新候选值result = a[i];k = 1;}}if(isThisDigit(result,n)) return result;else return 0;}int main(){cout<<test1(5)<<endl;cout<<test2(5)<<endl;cout<<test3(5)<<endl;return 0;}
