题目描述
链接: https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
输入一个非负整数数组, 把数组里所有数字拼接起来排出一个数, 打印能拼接出的数字中最小的一个.
示例1:
输入: [10, 2]
输出: “102”. 两个数字的排列可能为102, 210. 由于102小, 所以结果为102.
示例2:
输入: [3, 30, 34, 5, 9]
输出: ”3033459“
解题思路
我们以两个数字转化为的字符串(x, y)为例
- 当 x + y > y + x 时, x应该大于y, 即x应该在y的后面
- 当 x + y < y + x时, y应该大于x, 即y应该在x的后面
可以看出, 这个问题可以转化为自定义排序的问题. 再来验证一下是否对多个值通用:
输入数组: [3, 30, 34, 5 ,9].
首先判断3, 30, 由于 330 > 303, 所以30在前面, 结果为[30, 3, 34, 5 ,9]
然后判断3, 34, 由于334< 343, 所以3在前面, 结果为[30, 3, 34, 5 ,9]
判断34, 5, 由于345< 534, 所以34在前面, 结果为[30, 3, 34, 5 ,9]
最后判断5, 9. 由于59< 95, 所以5在前面, 结果为[30, 3, 34, 5 ,9]. 与答案一致.
代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
quickSort(strs, 0, strs.length - 1);
StringBuilder res = new StringBuilder();
for (String s : strs) {
res.append(s);
}
return res.toString();
}
// 使用快排
private void quickSort(String[] strs, int left, int right) {
if (left >= right) return;
int i = left, j = right;
String tmp = strs[i];
while (i < j) {
// 如果 j + left > left + j, 那么left就应该做左侧, j在右侧。所以j--, 比较下一个值
while ((strs[j] + strs[left]).compareTo(strs[left] + strs[j]) >= 0 && i < j) {
j--;
}
// 如果 i + left < left + i, 那么i应该在左侧, left在右侧。所以i++, 比较下一个值
while ((strs[i] + strs[left]).compareTo(strs[left] + strs[i]) <= 0 && i < j) {
i++;
}
// 找到两个要交换的值，将其交换
tmp = strs[i];
strs[i] = strs[j];
strs[j] = tmp;
}
strs[i] = strs[left];
strs[left] = tmp;
quickSort(strs, left, i - 1);
quickSort(strs, i + 1, right);
}
|