[Lc]面试题45把数组排成最小的数

题目

题解

这道题实际上是字符串排序，需要重新定义字符串大小的定义 ，具体的排序方法见注释

• 时间复杂度$O(nlog{n})$
• 空间复杂度$O(n)$，str_num和res

class Solution {
public:
    //定义符合该题的字符串比较函数
    //若字符串拼接a+b>b+a，则b要取小的数，b应当在前面
    //即b<a
    //sort是默认升序的，若要降序使用ab>ba
    static bool myCompare(const string &a, const string &b){
        string ab = a + b;
        string ba = b + a;
        return ab<ba;
    }
    string minNumber(vector<int>& nums) {
        string res;//存结果
        const int n = nums.size();
        if(n==0) return res;
        //把vector中每个int转化为string
        vector<string> str_nums(n);
        for(int i=0; i<n; ++i){
            str_nums[i] = to_string(nums[i]);
        }
        //按定义的字符串比较函数排序
        sort(str_nums.begin(), str_nums.end(), myCompare);
        //把结果挨个存入res
        for(int i=0; i<n; ++i){
            res.append(str_nums[i]);
        }
        return res;
    }
};