【题目描述】 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{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;
}
};