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

【题目描述】 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

【思路解析】

怎么样的排列顺序能够拼成最小数，A与剩余字符，如果A跟每个字符拼接都是A放在前面值更小，说明在最终的结果中A就应当放在最前，然后除去A在剩余字符中同样方法寻找。时间复杂度平方级别。

【代码】

python:

class Solution:
    def compare(self, init, cmp):
        if (int(init + cmp) >= int(cmp + init)):
            return True
        return False
    def PrintMinNumber(self, numbers):
        numbers = [str(i) for i in numbers]
        for i in range(len(numbers) - 1):
            for j in range(i + 1, len(numbers)):
                if self.compare(numbers[i], numbers[j]):
                    numbers[i], numbers[j] = numbers[j], numbers[i]
        return ''.join(numbers)

简化后：在python3中利用内置函数，简化程序，但是本质上与双层循环一致。
from functools import cmp_to_key
class Solution:
    def PrintMinNumber(self, numbers):
        numbers = [str(i) for i in numbers]
        numbers.sort(key=cmp_to_key(lambda x,y:int(x+y)-int(y+x)))
        return ''.join(numbers)

C++:
class Solution {
public:
static bool cmp(int a,int b){
         string A="";
         string B="";
         A+=to_string(a);
         A+=to_string(b);
         B+=to_string(b);
         B+=to_string(a);
         return A<B;
     }
     string PrintMinNumber(vector<int> numbers) {
         string  answer="";
         sort(numbers.begin(),numbers.end(),cmp);//此处可以用双层循环替换
         for(int i=0;i<numbers.size();i++){
             answer+=to_string(numbers[i]);
         }
         return answer;
     }
};