剑指 Offer 45. 把数组排成最小的数

题目链接：剑指 Offer 45. 把数组排成最小的数

方法：排序

解题思路

• 将数字转化为字符串数组，然后 \(sort()\)；
• cmp()函数

static bool cmp(string a, string b) {
    return a + b < b + a;
}

代码

// 写法一
class Solution {
public:
    static bool cmp(string a, string b) {
        return a + b < b + a;
    }
    string minNumber(vector<int>& nums) {
        int n = nums.size();
        vector<string> dp(n);
        for (int i = 0; i < n; i ++ ) dp[i] = to_string(nums[i]);
        sort(dp.begin(), dp.end(), cmp);
        for (int i = 1; i < n; i ++ ) dp[i] = dp[i - 1] + dp[i];
        return dp[n - 1];
    }
};

// 写法2，较慢
class Solution {
public:
    static bool cmp(int a, int b) {
        return to_string(a) + to_string(b) < to_string(b) + to_string(a);
    }
    string minNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        string ans;
        for (int i = 0; i < nums.size(); i ++ ) ans += to_string(nums[i]);
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(nlogn)\)；
空间复杂度：写法一：\(O(n)\)，写法二：\(O(1)\)，忽略排序时的调用栈。