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

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

/*
    本质上是一个排序问题。设数组nums中任意两数字的字符串为 x 和 y，则规定排序判断规则为：

    若拼接字符串 x + y > y + x，则 x“大于”y ；
    反之，若 x + y < y + x，则 x “小于”y ；

    其中，x “小于” y代表：排序完成后，数组中 x应在 y左边；“大于” 则反之。
    
    算法流程：
    1.初始化： 字符串列表 strs，保存各数字的字符串格式；
    2.列表排序： 应用以上 “排序判断规则” ，对 strs执行排序；
    3.返回值： 拼接 strs 中的所有字符串，并返回。

*/

方法1：c++自带排序函数，时间复杂度 O(N log N)，空间复杂度 O(N) 

string PrintMinNumber(vector<int> numbers) 
{
    vector<string> strs;
    string s;
    for(auto n:numbers)
    {
        strs.push_back(to_string(n));
    }
    sort(strs.begin(),strs.end(),[](string& s1,string& s2){return s1+s2<s2+s1;});//引用传递，所以要用begin和end指向向量容器的地址 
    for(auto i:strs)
    {
        s.append(i);	
    }   
    return s;
}

方法2：手写快排，时间复杂度 O(N log N)，空间复杂度 O(N) 

class Solution {
public:
    void quick_sort(vector<string>& s,int low,int high)
    {
        if(low>=high)
            return;

        int l=low,h=high;
        string x=s[low];///注意这里有递归，所以初始值不是s[0],而是s[low] 

        while(l<h)
        {		
            while((x+s[h])<=(s[h]+x)&&l<h)//这里要加等于号
                h--;
            s[l]=s[h];

            while((x+s[l])>=(s[l]+x)&&l<h)//这里要加等于号
                l++;      
            s[h]=s[l];	
        }
        s[l]=x;

        quick_sort(s,low,l-1);
        quick_sort(s,l+1,high);
    }
    
    string PrintMinNumber(vector<int> numbers) {
        vector<string> strs;
        string s;
        for(auto n:numbers)
        {
            strs.push_back(to_string(n));
        }
        quick_sort(strs,0,strs.size()-1);
        for(auto i:strs)
        {
            s.append(i);	
        }   
        return s;
    }
};