[[420230]]

C++ 里怎么一個(gè)簡(jiǎn)單的 ::std::sort 就能堆溢出呢?

BV1Z64y1a7P1 坑神截圖

這周力扣周賽照例去湊熱鬧。

前兩道題很快寫完了，T3T4讀了題...嗯，不憋了，等坑神的題解吧。

午時(shí)十二點(diǎn)，令我十分意外地發(fā)現(xiàn)坑神T2竟然罰時(shí)了好多次?

T2不就是重載一下 sort 的比較函數(shù)嗎?看坑神的b站錄象[1]，再看看評(píng)論，才知道 C++ 中的一個(gè)驚天大坑。得益于4個(gè)月來對(duì) y 總高質(zhì)量代碼風(fēng)格與良好書寫習(xí)慣的閱讀與模仿，我在考試時(shí)“幸運(yùn)”地避開了這個(gè)坑。

但還是很有必要記錄一下。

題目：找出數(shù)組中的第 K 大整數(shù)

給你一個(gè)字符串?dāng)?shù)組 nums 和一個(gè)整數(shù) k 。nums 中的每個(gè)字符串都表示一個(gè)不含前導(dǎo)零的整數(shù)。

返回 nums 中表示第 k 大整數(shù)的字符串。

注意：重復(fù)的數(shù)字在統(tǒng)計(jì)時(shí)會(huì)視為不同元素考慮。例如，如果 nums 是 ["1","2","2"]，那么 "2" 是最大的整數(shù)，"2" 是第二大的整數(shù)，"1" 是第三大的整數(shù)。

示例 1：

輸入：nums = ["3","6","7","10"], k = 4 
輸出："3" 
解釋： 
nums 中的數(shù)字按非遞減順序排列為 ["3","6","7","10"] 
其中第 4 大整數(shù)是 "3" 

示例 2：

輸入：nums = ["2","21","12","1"], k = 3 
輸出："2" 
解釋： 
nums 中的數(shù)字按非遞減順序排列為 ["1","2","12","21"] 
其中第 3 大整數(shù)是 "2" 

示例 3：

輸入：nums = ["0","0"], k = 2 
輸出："0" 
解釋： 
nums 中的數(shù)字按非遞減順序排列為 ["0","0"] 
其中第 2 大整數(shù)是 "0" 

提示：

• 1 <= k <= nums.length <=
• 1 <= nums[i].length <= 100
• nums[i] 僅由數(shù)字組成
• nums[i] 不含任何前導(dǎo)零

我的臨場(chǎng)作答

struct Num 
{ 
    string a; 
     
    bool operator< (const Num& t) const 
    { 
        if (a.size() != t.a.size()) return a.size() < t.a.size(); 
        for (int i = 0; i < a.size(); ++ i) 
        { 
            if (a[i] != t.a[i]) return a[i] < t.a[i]; 
        } 
        return false; 
    } 
}; 
 
class Solution { 
public: 
    string kthLargestNumber(vector<string>& nums, int k) { 
        vector<Num> S; 
        for (auto&& t: nums) 
        { 
            S.push_back({t}); 
        } 
 
        sort(S.begin(), S.end()); 
        return S[S.size() - k].a; 
    } 
}; 

經(jīng)驗(yàn)：

重載 sort 中，在 operator < 或者 cmp 中 a == b 時(shí)一定也得返回 false !如果不返回 false 而是 true 將造成堆棧溢出!

• “主要是因?yàn)槿绻鸻==b時(shí)return true的話，那么我們?cè)赼和b相等的時(shí)候，問a
• “原來，STL中的sort并非只是普通的快速排序，除了對(duì)普通的快速排序進(jìn)行優(yōu)化，它還結(jié)合了插入排序和堆排序。根據(jù)不同的數(shù)量級(jí)別以及不同情況，能自動(dòng)選用合適的排序方法。當(dāng)數(shù)據(jù)量較大時(shí)采用快速排序，分段遞歸。一旦分段后的數(shù)據(jù)量小于某個(gè)閥值，為避免遞歸調(diào)用帶來過大的額外負(fù)荷，便會(huì)改用插入排序。而如果遞歸層次過深，有出現(xiàn)最壞情況的傾向，還會(huì)改用堆排序。”
• 坑神掉進(jìn)了這個(gè)坑：【算法實(shí)況】又血崩了，這種題目完全沒經(jīng)驗(yàn)烏烏 - 力扣周賽 - LeetCode Weekly 256[2]

此外，一些關(guān)于重載效率的對(duì)比如下：

• 我的題解性能(struct重載operator<)：執(zhí)行用時(shí) 236ms 內(nèi)存消耗 76.9MB
• 力扣官方題解性能(lambda重載sort)：執(zhí)行用時(shí) 132ms 內(nèi)存消耗 53.8MB
• 巨佬墨染空[3]題解性能(重載sort)：執(zhí)行用時(shí) 592ms 內(nèi)存消耗 341.7MB

代碼如下。這讓我感覺很費(fèi)解。

// 力扣官方題解 
class Solution { 
public: 
    string kthLargestNumber(vector<string>& nums, int k) { 
        nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), [](const string& u, const string& v "") { 
            return u.size() > v.size() || (u.size() == v.size() && u > v); 
        }); 
        return nums[k - 1]; 
    } 
}; 
 
// 巨佬墨染空題解 
bool inline cmp(string x, string y) { 
 if (x.size() != y.size()) return x.size() > y.size(); 
 return x > y; 
} 
 
class Solution { 
public: 
  
    string kthLargestNumber(vector<string>& a, int k) { 
     vector<string> s = a;  // 我將此賦值去掉，也沒有提升性能 
     sort(s.begin(), s.end(), cmp); 
     return s[k - 1]; 
    } 
}; 

參考資料

[1]坑神的b站錄象: https://www.bilibili.com/video/BV1Z64y1a7P1

[2]【算法實(shí)況】又血崩了，這種題目完全沒經(jīng)驗(yàn)烏烏 - 力扣周賽 - LeetCode Weekly 256: https://www.bilibili.com/video/BV1Z64y1a7P1?p=1

[3]墨染空: https://leetcode-cn.com/u/mo-ran-kong/