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

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

创新互联公司专注为客户提供全方位的互联网综合服务，包含不限于成都网站设计、做网站、德城网络推广、小程序设计、德城网络营销、德城企业策划、德城品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联公司为所有大学生创业者提供德城建站搭建服务，24小时服务热线：18982081108，官方网址：www.cdcxhl.com

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. 
  
  
  
  
  2. 输出："3" 
    3. 
  
  
  
  
  3. 解释： 
    4. 
  
  
  
  
  4. nums 中的数字按非递减顺序排列为 ["3","6","7","10"] 
    5. 
  
  
  
  
  5. 其中第 4 大整数是 "3" 
    6.

示例 2：

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

示例 3：

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

提示：

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

我的临场作答

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

经验：

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

参考资料

[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/

当前题目：C++里一个简单的::std::sort怎么就能造成堆溢出呢？
文章网址：http://www.shufengxianlan.com/qtweb/news11/280361.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

服务器托管知识

同城分类信息

乐山网站建设　　 　优化排名　　 　响应式网站　　 　成都做网站　　 　成都网站设计　　 　响应式网站设计　　 　成都网站优化　　 　成都做商城网站　　 　成都品牌网站建设　　 　小谭网创广告　　 　普能电气　　 　申请域名　　 　专业网站建设　　 　深圳纱窗安装　　 　软文发稿　　 　证企宝　　 　wap网站建设　　 　乐山服务器托管　　 　成都小程序开发　　 　网站优化排名推广