本文共 2872 字，大约阅读时间需要 9 分钟。

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

样例： 
[1,2,3,2,2],5 
返回：2

其实就是求超过数组一半的元素问题，剑指offer上有。

方法一：利用partition方法

class Gift {public:    int getValue(vector
   
     gifts, int n) {        if(n <= 0)            return -1;        int start = 0;        int end = n - 1;        int middle = (end - start) >> 1;        int index = -1;        index = partition(gifts, start, end);        while(index < middle){            if(index > middle){ //index>middle，说明中位数在左边，我们需要左调整end                end = index - 1;                index = partition(gifts, start, end);            }            else{  //index <= middle，说明中位数在右边，需要右调整start                start = index + 1;                index = partition(gifts, start, end);              }        }        return check_more_than_half(gifts, n, gifts[middle]);    }    int partition(vector
    
      gifts, int start, int end){        int small = start - 1; //在这行和下面这行，我想把我自己叫哥了，经常由于写代码写的快把start写成0，因为这个耽搁时间我真是醉了...        for(int index=start; index