天生我材必有用，千金散尽还复来“微信红包”

题目描述

链接&＃xff1a;https://www.nowcoder.com/questionTerminal/fbcf95ed620f42a88be24eb2cd57ec54
来源&＃xff1a;牛客网

[编程题]微信红包.

热度指数&＃xff1a;23432时间限制&＃xff1a;C/C&＃43;&＃43; 3秒&＃xff0c;其他语言6秒空间限制&＃xff1a;C/C&＃43;&＃43; 32M&＃xff0c;其他语言64M
算法知识视频讲解
春节期间小明使用微信收到很多个红包&＃xff0c;非常开心。在查看领取红包记录时发现&＃xff0c;某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现&＃xff0c;要求算法尽可能高效。

给定一个红包的金额数组gifts及它的大小n&＃xff0c;请返回所求红包的金额。

若没有金额超过总数的一半&＃xff0c;返回0。

测试样例&＃xff1a;

[1,2,3,2,2],5
返回&＃xff1a;2

思路解析

第一种排序思路&＃xff0c;如果一个数出现次数超过一半了&＃xff0c;排序过后&＃xff0c;必然排在中间&＃xff0c;则最后遍历整个数组查看是否符合即可。

class Gift { public: int getValue(vector<int> gifts, int n) { sort(gifts.begin(), gifts.end()); //超过一半的数排序之后必然排在中间 int middle &＃61; gifts[n / 2]; int count &＃61; 0;for(int i &＃61; 0; i < n; i&＃43;&＃43;) { //统计排在中间的数的个数 if(gifts[i] &＃61;&＃61; middle) { count&＃43;&＃43;; } }//如果个数大于一半&＃xff0c;则存在超过一半的数 if(count > n / 2) return middle; elsereturn 0; }
};


第二种思路可以用map统计每个数字出现的次数&＃xff0c;最后判断有没有超过一半的数字。

class Gift { public: int getValue(vector<int> gifts, int n) { map<int,int> count;int middle &＃61; gifts.size() / 2;for(const auto& e : gifts) {&＃43;&＃43;count[e]; }for(const auto& e : count) { if(e.second >&＃61; middle) return e.first; }return 0;}
};