9006531組成最大數值，179. 最大數

鏈接：

自定義排序：
想法

為了構建最大數字，我們希望越高位的數字越大越好。

9006531組成最大數值。算法

首先，我們將每個整數變成字符串。然后進行排序。

如果僅按降序排序，有相同的開頭數字的時候會出現問題。比方說，樣例 2 按降序排序得到的數字是 9534330395343303 ，然而交換 33 和 3030 的位置可以得到正確答案 95343309534330 。因此，每一對數在排序的比較過程中，我們比較兩種連接順序哪一種更好。我們可以證明這樣的做法是正確的：

假設（不是一般性），某一對整數 aa 和 bb ，我們的比較結果是 aa 應該在 bb 前面，這意味著 a\frown b > b\frown aa?b>b?a ，其中 \frown? 表示連接。如果排序結果是錯的，說明存在一個 cc ， bb 在 cc 前面且 cc 在 aa 的前面。這產生了矛盾，因為 a\frown b > b\frown aa?b>b?a 和 b\frown c > c\frown bb?c>c?b 意味著 a\frown c > c\frown aa?c>c?a 。換言之，我們的自定義比較方法保證了傳遞性，所以這樣子排序是對的。

一旦數組排好了序，最“重要”的數字會在最前面。有一個需要注意的情況是如果數組只包含 0 ，我們直接返回結果 00 即可。否則，我們用排好序的數組形成一個字符串并返回。

最強的大腦179關最大的數字，復雜度分析

• 時間復雜度：O(nlgn)

• 空間復雜度：O(n)

注意點：

1.自定義排序，防止3,30這種case

目前最大的數是多少？2.最高位為0需要返回0即可

3.拼接后的數字可能超過int最大值，因此需要返回std::string類型

class Solution {                                                                                    public:// 自定義排序保證3,30 330和303這種字符的順序static bool compare(const std::string& a, const std::string& b) {                                  const std::string& a_b = a + b;                                                         const std::string& b_a = b + a;                                                         return a_b > b_a;                                                                       }                                                                                           string largestNumber(vector<int>& nums) {                                                   std::string big_value;                                                                  if (nums.size() <= 0) {                                                                 return big_value;                                                                   }                                                                                       vector<std::string> str_nums;                                                           str_nums.reserve(nums.size());// 將int變為std::stringfor (auto ite : nums) {                                                                 str_nums.push_back(to_string(ite));                                                 }                                                                                       sort(str_nums.begin(), str_nums.end(), compare);// 因為排好序的數字可能會超過int最大范圍，因此需要返回std::stringfor (auto ite : str_nums) {                                                                  big_value += ite;                                                                   }// 如果最高位為0,則直接返回0就可以，防止拼接成0000這種字符串if (str_nums.size() >= 1 && str_nums[0] == std::string("0")) {big_value = '0';}return big_value;                                                                       }                                                                                           
};

?