第 45 题：把数组排成最小的数
传送门：把数组排成最小的数，牛客网 online judge 地址。
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组
[3, 32, 321]，则打印出这 3 个数字能排成的最小数字321323。样例：
输入：
[3, 32, 321]输出：
321323注意：输出数字的格式为字符串。
同 LeetCode 第 179 题，最大数。
Java 代码：
import java.util.Arrays;
public class Solution {
public String PrintMinNumber(int[] numbers) {
int len = numbers.length;
if (len == 0) {
return "";
}
String[] numsStr = new String[len];
for (int i = 0; i < len; i++) {
numsStr[i] = numbers[i] + "";
}
Arrays.sort(numsStr, (a, b) -> (a + b).compareTo(b + a));
StringBuilder builder = new StringBuilder();
for (int i = 0; i < len; i++) {
builder.append(numsStr[i]);
}
return builder.toString();
}
public static void main(String[] args) {
int[] nums = new int[]{3, 32, 321};
Solution solution = new Solution();
String printMinNumber = solution.PrintMinNumber(nums);
System.out.println(printMinNumber);
}
}
说明：其实就定义自定义排序规则。Python3 想用 cmp 而不是 key 的话，需要 from functools import cmp_to_key ，然后 sort 或者 sorted 的时候 key = cmp_to_key(your_comparator) 。
Python 代码：
class Solution(object):
def printMinNumber(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
if len(nums) == 0:
return ''
# 自定义排序规则
from functools import cmp_to_key
key_func = cmp_to_key(lambda a, b: int(a + b) - int(b + a))
result = sorted(map(str, nums), key=key_func)
return ''.join(result)
if __name__ == '__main__':
list1 = [7, -8, 5, 4, 0, -2, -5]
# 要求：1、正数在前负数在后
# 2、正数从小到大
# 3、负数从大到小
result = sorted(list1, key=lambda x: (x < 0, abs(x)))
print(result)
s = 'asdf234GDSdsf23' # 排序:小写-大写-奇数-偶数
print(
"".join(
sorted(
s,
key=lambda x: (
x.isdigit(),
x.isdigit() and int(x) %
2 == 0,
x.isupper(),
x))))
另一种写法：
Python 代码：
class NumCompare(str):
# 注意：这里继承 str 类
def __lt__(self, other):
return self + other < other + self
class Solution(object):
def printMinNumber(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
if len(nums) == 0:
return ''
# 自定义排序规则
result = sorted(map(str, nums), key=NumCompare)
return ''.join(result)
