服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++里一个简单的 ::std::sort 怎么就能造成堆溢出呢?

C++里一个简单的 ::std::sort 怎么就能造成堆溢出呢?

2021-08-30 23:51Piper蛋窝Piper蛋 C/C++

T2不就是重载一下 sort 的比较函数吗?看坑神的b站录象[1],再看看评论,才知道 C++ 中的一个惊天大坑。得益于4个月来对 y 总高质量代码风格与良好书写习惯的阅读与模仿,我在考试时“幸运”地避开了这个坑。

C++里一个简单的 ::std::sort 怎么就能造成堆溢出呢?

C++ 里怎么一个简单的 ::std::sort 就能堆溢出呢?

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:

  1. 输入:nums = ["3","6","7","10"], k = 4 
  2. 输出:"3" 
  3. 解释: 
  4. nums 中的数字按非递减顺序排列为 ["3","6","7","10"
  5. 其中第 4 大整数是 "3" 

示例 2:

  1. 输入:nums = ["2","21","12","1"], k = 3 
  2. 输出:"2" 
  3. 解释: 
  4. nums 中的数字按非递减顺序排列为 ["1","2","12","21"
  5. 其中第 3 大整数是 "2" 

示例 3:

  1. 输入:nums = ["0","0"], k = 2 
  2. 输出:"0" 
  3. 解释: 
  4. nums 中的数字按非递减顺序排列为 ["0","0"
  5. 其中第 2 大整数是 "0" 

提示:

  • 1 <= k <= nums.length <=
  • 1 <= nums[i].length <= 100
  • nums[i] 仅由数字组成
  • nums[i] 不含任何前导零

我的临场作答

  1. struct Num 
  2.     string a; 
  3.      
  4.     bool operator< (const Num& t) const 
  5.     { 
  6.         if (a.size() != t.a.size()) return a.size() < t.a.size(); 
  7.         for (int i = 0; i < a.size(); ++ i) 
  8.         { 
  9.             if (a[i] != t.a[i]) return a[i] < t.a[i]; 
  10.         } 
  11.         return false
  12.     } 
  13. }; 
  14.  
  15. class Solution { 
  16. public
  17.     string kthLargestNumber(vector<string>& nums, int k) { 
  18.         vector<Num> S; 
  19.         for (auto&& t: nums) 
  20.         { 
  21.             S.push_back({t}); 
  22.         } 
  23.  
  24.         sort(S.begin(), S.end()); 
  25.         return S[S.size() - k].a; 
  26.     } 
  27. }; 

经验:

重载 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

代码如下。这让我感觉很费解。

  1. // 力扣官方题解 
  2. class Solution { 
  3. public
  4.     string kthLargestNumber(vector<string>& nums, int k) { 
  5.         nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), [](const string& u, const string& v "") { 
  6.             return u.size() > v.size() || (u.size() == v.size() && u > v); 
  7.         }); 
  8.         return nums[k - 1]; 
  9.     } 
  10. }; 
  11.  
  12. // 巨佬墨染空题解 
  13. bool inline cmp(string x, string y) { 
  14.  if (x.size() != y.size()) return x.size() > y.size(); 
  15.  return x > y; 
  16.  
  17. class Solution { 
  18. public
  19.   
  20.     string kthLargestNumber(vector<string>& a, int k) { 
  21.      vector<string> s = a;  // 我将此赋值去掉,也没有提升性能 
  22.      sort(s.begin(), s.end(), cmp); 
  23.      return s[k - 1]; 
  24.     } 
  25. }; 

参考资料

[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

延伸 · 阅读

精彩推荐