C++ 里怎么一个简单的 ::std::sort 就能堆溢出呢?
BV1Z64y1a7P1 坑神截图
这周力扣周赛照例去凑热闹。
前两道题很快写完了，T3T4读了题...嗯，不憋了，等坑神的题解吧。
午时十二点，令我十分意外地发现坑神T2竟然罚时了好多次?
T2不就是重载一下 sort 的比较函数吗?看坑神的b站录象[1]，再看看评论，才知道 C++ 中的一个惊天大坑。得益于4个月来对 y 总高质量代码风格与良好书写习惯的阅读与模仿，我在考试时“幸运”地避开了这个坑。
但还是很有必要记录一下。
题目：找出数组中的第 K 大整数
给你一个字符串数组 nums 和一个整数 k 。nums 中的每个字符串都表示一个不含前导零的整数。
返回 nums 中表示第 k 大整数的字符串。
注意：重复的数字在统计时会视为不同元素考虑。例如，如果 nums 是 ["1","2","2"]，那么 "2" 是最大的整数，"2" 是第二大的整数，"1" 是第三大的整数。
示例 1：
- 输入：nums=["3","6","7","10"],k=4
- 输出："3"
- 解释：
- nums中的数字按非递减顺序排列为["3","6","7","10"]
- 其中第4大整数是"3"
示例 2：
- 输入：nums=["2","21","12","1"],k=3
- 输出："2"
- 解释：
- nums中的数字按非递减顺序排列为["1","2","12","21"]
- 其中第3大整数是"2"
示例 3：
- 输入：nums=["0","0"],k=2
- 输出："0"
- 解释：
- nums中的数字按非递减顺序排列为["0","0"]
- 其中第2大整数是"0"
提示：
- 1 <= k <= nums.length <=
- 1 <= nums[i].length <= 100
- nums[i] 仅由数字组成
- nums[i] 不含任何前导零
我的临场作答
- structNum
- {
- stringa;
- booloperator<(constNum&t)const
- {
- if(a.size()!=t.a.size())returna.size()<t.a.size();
- for(inti=0;i<a.size();++i)
- {
- if(a[i]!=t.a[i])returna[i]<t.a[i];
- }
- returnfalse;
- }
- };
- classSolution{
- public:
- stringkthLargestNumber(vector<string>&nums,intk){
- vector<Num>S;
- for(auto&&t:nums)
- {
- S.push_back({t});
- }
- sort(S.begin(),S.end());
- returnS[S.size()-k].a;
- }
- };
经验：
重载 sort 中，在 operator < 或者 cmp 中 a == b 时一定也得返回 false !如果不返回 false 而是 true 将造成堆栈溢出!
- “主要是因为如果a==b时return true的话，那么我们在a和b相等的时候，问a
- “原来，STL中的sort并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。”
- 坑神掉进了这个坑：【算法实况】又血崩了，这种题目完全没经验乌乌 - 力扣周赛 - LeetCode Weekly 256[2]
此外，一些关于重载效率的对比如下：
- 我的题解性能(struct重载operator<)：执行用时 236ms 内存消耗 76.9MB
- 力扣官方题解性能(lambda重载sort)：执行用时 132ms 内存消耗 53.8MB
- 巨佬墨染空[3]题解性能(重载sort)：执行用时 592ms 内存消耗 341.7MB
代码如下。这让我感觉很费解。
- //力扣官方题解
- classSolution{
- public:
- stringkthLargestNumber(vector<string>&nums,intk){
- nth_element(nums.begin(),nums.begin()+k-1,nums.end(),[](conststring&u,conststring&v""){
- returnu.size()>v.size()||(u.size()==v.size()&&u>v);
- });
- returnnums[k-1];
- }
- };
- //巨佬墨染空题解
- boolinlinecmp(stringx,stringy){
- if(x.size()!=y.size())returnx.size()>y.size();
- returnx>y;
- }
- classSolution{
- public:
- stringkthLargestNumber(vector<string>&a,intk){
- vector<string>s=a;//我将此赋值去掉，也没有提升性能
- sort(s.begin(),s.end(),cmp);
- returns[k-1];
- }
- };
参考资料
[1]坑神的b站录象: https://www.bilibili.com/video/BV1Z64y1a7P1
[2]【算法实况】又血崩了，这种题目完全没经验乌乌 - 力扣周赛 - LeetCode Weekly 256: https://www.bilibili.com/video/BV1Z64y1a7P1?p=1
[3]墨染空: https://leetcode-cn.com/u/mo-ran-kong/
原文链接：https://mp.weixin.qq.com/s/H3CFtlZZp0hw6xjIpLB1Zg
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。