题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思路
本题主要是找排序方法判断所有数的顺序方法。
思路1
- 1.全部用个位数+长度补齐，比如{3, 32, 321}补齐成{3331, 3222, 3213}，{1, 11, 111}补齐成{1111, 1112, 1113} o(nlogn)
- 2.排序，从小到大取下标 o(nlogn)
- 3.根据下标的数组装结果
思路2
- 1.比较n1与n2，转成字符串s1与s2
- 2.比较s1s2与s2s1大小，小的放前面
- 3.依次输出所有字符串
#思路一
def number_len(n):
res = 0
while n:
n //= 10
res += 1
return res
def PrintMinNumber(numbers):
# write code here
if len(numbers) == 1: return numbers[0]
max_len = number_len(max(numbers))
map = {}
for i in range(len(numbers)):
n = numbers[i]
pad = n % 10
n_len = number_len(n)
for j in range(max_len-n_len):
n = n*10+pad
map[n*10+n_len] = i
keys = sorted(map.keys())
res = numbers[map[keys[0]]]
for i in range(1, len(keys)):
n = numbers[map[keys[i]]]
res = res * 10 ** number_len(n) + n
return res
# map = {numbers[i]:i for i in range(len(numbers))}
print(PrintMinNumber([11,1,111]))#思路2：
import functools
def compare(s1, s2):
if s1+s2 < s2+s1:
return -1
elif s1+s2 == s2+s1:
return 0
else:
return 1
def PrintMinNumber(numbers):
# write code here
if not numbers: return ''
if len(numbers) == 1: return numbers[0]
str_numbers = [str(n) for n in numbers]
return ''.join(sorted(str_numbers, key=functools.cmp_to_key(compare)))
print(PrintMinNumber([32, 3, 321]))
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me.