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

贪心+排序：等于数组中任意两个字符串a,b，如果a + b < b + a, 显然我们希望a排在b的前面，因为a排在前面可以使结果更小。那么可以用内排序（插入，冒泡等）的方法，让局部的字符串最小（贪心）。

初始代码：

public:
    string PrintMinNumber(vector<int> numbers) {
        string res = "";
        vector<string> strs;
        for(int i = 0; i < numbers.size(); i ++)
            strs.push_back(toStr(numbers[i]));
        for(int i = 0; i < strs.size(); i ++){
            int min = i;
            for(int j = i+1; j < strs.size(); j ++){
                if(compare(strs[min], strs[j]))
                    min = j;
            }
            string temp = strs[i];
            strs[i] = strs[min];
            strs[min] = temp;
        }
        for(int i = 0; i < strs.size(); i ++)
            res += strs[i];
        return res;
    }
    
    bool compare(string a, string b){// a>b true
        if(!a.size() || !a.size())
            return false;
        int i;
        for(i = 0; i < a.size() && i < b.size(); i ++){
            if(a[i] > b[i])
                return true;
            else if(a[i] < b[i])
                return false;
        }
        if(a.size() > b.size())
            return compare(a.substr(i), b);
        else if(a.size() < b.size())
            return compare(a, b.substr(i));
        else
            return false;
    }
    
    string toStr(int x){
        string s = "";
        stack<char> ss;
        if(!x)
            return "0";
        while(x){
            ss.push('0' + (x % 10));
            x /= 10;
        }
        while(!ss.empty()){
            s += ss.top();
            ss.pop();
        }
        return s;
    }
};

改进：

1. to_string()可以直接数字转字符串。。。

2. 运用冒泡的思想，a + b < b + a 就可以比较字符串相加的大小。。。

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        string res = "";
        vector<string> strs;
        for(int i = 0; i < numbers.size(); i ++)
            strs.push_back(to_string(numbers[i]));
        for(int i = strs.size(); i > 0; i --){
            for(int j = 1; j < strs.size(); j ++){
                if(strs[j - 1] + strs[j] > strs[j] + strs[j - 1]){//a + b > b + a 
                    string temp = strs[j - 1];
                    strs[j - 1] = strs[j];
                    strs[j] = temp;
                }
            }
        }
        for(int i = 0; i < strs.size(); i ++)
            res += strs[i];
        return res;
    }
};