题解 | 微信红包

#include <unordered_set>
class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        unordered_map<int, int> up;
        for (auto& gift : gifts) {
            up[gift]++;
        }

        int count = n / 2;
        for (auto& pair : up) {
            if (pair.second > count) {
                return pair.first;
            }
        }
        return 0;
    }
};

解题思路

使用unordered_map来存储。查找的时间也很快。gift作为键，每次gift一出现其值就加一。其值就是gift出现的总次数。一旦超过n的一半提前返回。因为题目描述的只有一种金额的数量会超过。