把数组排成最小的数（C++）

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

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

1. 输出结果可能非常大，所以你需要返回一个字符串而不是整数
2. 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

数据范围:

0<=len(numbers)<=100

输入：
[11,3]
返回值：
"113"

输入：
[]
返回值：
""

输入：
[3,32,321]
返回值：
"321323"

我们对给出的数组进行排序，当然，排序不是对int类型的整个大小进行判断排序，而是判断相同的位数的大小关系，比如[11,3]，11的最高位是1，而3的最高位是3，此时1小于3，那么排序后的结果是[11,3]。又例如[3,32,321]，两位数之间进行比较排序，先比较3和32，由于最高位均相同，那么则比较第二位，由于3已经遍历完，而32的第二位是2，针对32这个数，2小于该位之前的所有元素，则表示32比3要小，否则只要2大于该位之前的任意一个元素，都表示该数比3大。因为排成一个数，323比332要小，而如果32变成3334，4比其之前的数都大，那么此时33343肯定是大于33334的。根据上述原理，[3,32,321]的最终排序结果为[321,32,3]。

class Solution {
  public:
    //判断str第index位置的元素与之前元素的大小关系
    //返回-1表示index元素之前的元素都是相同的元素，返回0表示str比跟其比较的字符串要小，返回1表示str比跟其比较的字符串要大
    int CurStrIndexSize(const string& str, int index) {
        bool flag = false;//用于判断index前面的字符是否与index位置字符相同，默认相同
        for (int k = 0; k < index; k++)
            if (str[k] != str[index])
                flag = true;
        //如果不相同，则判断index位置的字符与之前字符的大小关系
        if (flag) {
            for (int k = 0; k < index; k++)
                if (str[k] < str[index])
                    return 1;
            return 0;
        }
        return -1;
    }


    //根据每个整数最高位来判断大小，返回true表示n1小，返回false表示n2小。
    bool IsSize(int n1, int n2) {
        int i = 0, j = 0;
        string str1 = to_string(n1);
        string str2 = to_string(n2);
        while (i < str1.size() || j < str2.size()) {
            //当str1已经遍历完时
            if (i >= str1.size()) {
                if (CurStrIndexSize(str2, j) == 1)
                    return true;
                else if (CurStrIndexSize(str2, j) == 0)
                    return false;
            }
            
            //当str2已经遍历完时
            if (j >= str2.size()) {
                if (CurStrIndexSize(str1, i) == 1)
                    return false;
                else if (CurStrIndexSize(str1, i) == 0)
                    return true;
            }
            
            //用于判断当str1和str2均未遍历完时，比较i，j位置的字符大小关系
            if (i < str1.size() && j < str2.size() && str1[i] != str2[j]) {
                if (str1[i] > str2[j])
                    return false;
                return true;
            }
            i++;
            j++;
        }
        return false;
    }

    string PrintMinNumber(vector numbers) {
        //冒泡排序
        for (int i = 0; i < numbers.size(); i++) {
            for (int j = 0; j < numbers.size() - i - 1; j++) {
                if (numbers[j] == numbers[j + 1])continue;
                if (!IsSize(numbers[j], numbers[j + 1])) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
        string res;
        for (auto&& number : numbers)
            res += to_string(number);
        return res;
    }
};

将数字放入数组，利用数组的排序函数sort（可以根据自定义的规则来排序），排序后越小的数放在越前面，这样到最后的排成数字才能最小

TIPS：std::sort要求函数对象必须为静态/全局函数指针，非静态成员函数指针不能直接传递给std::sort。

class Solution {
  public:
    static bool cmp(const string& str1,const string& str2)
    {
        string s1 = str1 + str2;
        string s2 = str2 + str1;
        return s1 < s2;
    }

    string PrintMinNumber(vector numbers) {
        vector strs;
        for(auto&& number:numbers)
            strs.push_back(to_string(number));
        
        sort(strs.begin(),strs.end(),cmp);//使用自定义比较规则将string中的元素排序
        string res;
        for(auto&& str: strs)
            res += str;
        return res;
    }
};