【剑指 offer】把数组排列成最小的数

1、题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例如输入数组[3, 32, 321]，则打印出这3个数字能排成的最小数字321323。

样例

输入：[3, 32, 321]
输出：321323

• 注意：输出数字的格式为字符串。

2、问题描述：

3、问题关键：

4、C++代码：

算法1：

class Solution {
public:
    static bool myCmp(int a, int b) {
        if (to_string(a) + to_string(b) < to_string(b) + to_string(a)) 
            return true;
        else
            return false;
    }
    string printMinNumber(vector<int>& nums) {
        string str;
        if (!nums.size()) return str;
        sort(nums.begin(), nums.end(), myCmp);
        for (int i = 0; i < nums.size(); i ++)
            str += to_string(nums[i]);
        
        return str;
    }
};

算法2:

class Solution {
public:
    void mySwap(int &a, int &b) {
        if (to_string(a) + to_string(b) > to_string(b) + to_string(a))
            swap(a, b);
    }
    string printMinNumber(vector<int>& nums) {
        string str;
        if (!nums.size()) return str;
        for (int i = 0; i < nums.size(); i ++) 
            for (int j = i; j < nums.size(); j ++)
                mySwap(nums[i], nums[j]);
        for (int i = 0; i < nums.size(); i ++) 
            str += to_string(nums[i]);
        
        return str;
    }
};