题解 | #把数组排成最小的数#

第七十一题

知道把什么数放在前面得到的值最小。

答案重写的排序就是拼接起来更小的，最好从数学的角度理解一下。

看一下下面四种怎么拼接。

第一种 第一位两个都不一样，则直接选择第一位小的放前面即可

321,111

123,111

321,333

第二三种 第一位都一样，第二位一个小，一个大

也就是说，第一位一样的时候，扔掉第一位

23,11

21,33

再重新进行比较，这样就找到了递归比较的条件

假设

123123111,123123122

两个比较

123123都一样

所以只剩下111比较122。1也一样，就是11比22，所以11放前面。

第四种 一各数长一个数短

第四种1 删不完，方法同上，先把一样的数字删掉，在比较

1234 125，就变成34比5 所以1234放前面

123 13 就变成23 比3 所以123 放前面

第四种2 全删完了，就要特殊考虑，比较剩下的数，和原数第一个数谁大

2115 211：都删211 变为5和没有，这个时候看5和2谁小 所以是2112115

9851 985：都删985，变为1和没有，比较1和9，所以是9851985

答案：修改比较函数

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        // 位数已经确定了，所以要把第一位最小的数放前面
        vector<string> str;
        for (int i=0;i<numbers.size();i++)
            str.push_back(to_string(numbers[i]));
        
        // 答案 重写sort的比较函数返回定义，修改为拼接两个字最小的放前面，最后直接遍历拼接
        sort(str.begin(), str.end(), compare);
        
        string ret = "";
        for (int i=0;i<str.size();i++) 
            ret += str[i];
        return ret;
    }
    
    static bool compare(string a, string b) {
        return a + b < b + a;
    }
};