数组中出现次数超过一半的数字

找出一个数组中出现次数超过一半的数字

   春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
   给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。
若没有金额超过总数的一半，返回0。

这个题目实质上是求一个数组中出现次数超过一般的数字的数量，因此我们可以很快想到在如果一个数字在一个序列中出现的次数超过一半，则说明这个数字的数量比其他任何数字都要多，因此在按序分布上这个数字一定是中位数，是充分条件。但是呢，一个序列中的中位数，不一定就是出现次数超过一半的数字不是必要条件，因此当我们找到了中位数之后，还需要进行统计这个数字出现的次数，判断是不是大于等于序列长度的一半。

好了思路说完了。下面贴代码

#include <algorithm>
class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        sort(gifts.begin(),gifts.begin());
        vector<int>::iterator it = gifts.begin();
        int mid = *(it + gifts.size()/2);
        int midnum = 0;
        for(;it!=gifts.end();it++)
        {
            if(*it == mid) midnum++;    
        }
        if(midnum <gifts.size()/2) return 0;
        else return mid;
    }
};