Question source

题目描述

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

1. 解题思路:暴力

假设n个整数的索引为[0...n-1],如果我们对这n个索引进行全排列,然后再对每次全排列进行组织一下结果,选取最小的即为答案。

Complexity

  • 时间复杂度:O(N*N!),全排列的时间复杂度为N!,每次排列结果需要遍历一次nums数组
  • 空间复杂度:O(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
void perm(int pos, vector<int> &num, string &ret) {
if (pos + 1 == num.size()) {
// 一次全排列的结果
string tmp = "";
for (int val : num) {
tmp += to_string(val);
}
ret = min(ret, tmp);
return;
}
for (int i = pos; i < num.size(); ++i) {
swap(num[pos], num[i]);
perm(pos+1, num, ret);
swap(num[pos], num[i]);
}
}
string PrintMinNumber(vector<int> nums) {
string ret(nums.size(), '9'); // nums.size()个'9'
perm(0, nums, ret);
return ret;
}
};

2. 解题思路:贪心,排序剪枝

显然方法一出现了太多无关的排列,我们需要一个最小的数,细想一下可知,如果有两个字符串a,b,如果a + b < b + a, 显然我们希望a排在b的前面,因为a排在前面可以使结果更小。于是我们就自定义排序规则,使得 numbers 中字符串都满足如上规则,那么,最后的字符串数组中字符串拼接的数字肯定是最小的。

算法步骤:

  1. numbers 转化为 numbers

  2. 自定义上述排序规则;

  3. 整合结果

Complexity

  • 时间复杂度:O(NlogN), 采用了排序
  • 空间复杂度:O(N)

Code

1
2
3
4
5
6
7
8
9
# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers: return ''
numbers = list(map(str,numbers))
numbers.sort(cmp=lambda x,y:cmp(x + y, y + x))
return ''.join(numbers).lstrip('0') or '0'

⚠️

1
2
3
4
5
6
7
# Python lstrip() 方法用于截掉字符串左边的空格或指定字符。
str.lstrip([chars]) # chars --指定截取的字符。

# cmp(x,y) 函数用于比较2个对象,如果 x < y 返回 -1, 如果 x == y 返回 0, 如果 x > y 返回 1。
# 以上实例运行后输出结果为:
cmp(80, 100) : -1
cmp(180, 100) : 1

参考