179. 最大数

链接:

自定义排序:
想法

为了构建最大数字,我们希望越高位的数字越大越好。

算法

首先,我们将每个整数变成字符串。然后进行排序。

如果仅按降序排序,有相同的开头数字的时候会出现问题。比方说,样例 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 即可。否则,我们用排好序的数组形成一个字符串并返回。

复杂度分析

  • 时间复杂度: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::string
            for (auto ite : nums) {                                                                 
                str_nums.push_back(to_string(ite));                                                 
            }                                                                                       
            sort(str_nums.begin(), str_nums.end(), compare);
            // 因为排好序的数字可能会超过int最大范围,因此需要返回std::string
            for (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;                                                                       
        }                                                                                           
};

 

版权声明:本文为INGNIGHT原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/INGNIGHT/article/details/102508780