输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
1
2
3
4
5
6
7
| 示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
|
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
这道题的目的：尽可能让高位数字为小数，单个位上的数字大的，尽可能放在低位上
算法：使用排序的方式，按照字典序对字符串进行排序：
字典序：比较两个字符串s1和s2：按照每个相同位置上的字符进行比较，如果位置1上的两个字符的字典序不同，则字典序小的排在前面，如果字典序相同，则继续比较下面的一位
比如：
1
2
3
4
5
6
7
8
9
| 比较：102和120
第一位相同-->比较第二位
第二位：0<2
所以：102 < 120
-------------------
比较：5和123
第一位：5>1
所以：123 < 5
|
解法1，使用小根堆的方式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public String minNumber(int[] nums) {
PriorityQueue<String> queue = new PriorityQueue<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return (s1 + s2).compareTo(s2 + s1);
}
});
for (int i:nums) {
queue.offer("" + i);
}
StringBuilder result = new StringBuilder();
while(!queue.isEmpty()){
result.append(queue.poll());
}
return result.toString();
}
}
|
解法2，直接对数组进行排序：
1
2
3
4
5
6
7
8
9
10
11
12
| public static String minNumber(int[] nums){
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = nums[i]+"";
}
Arrays.sort(strs, (x,y)->(x + y).compareTo(y + x));
StringBuilder result = new StringBuilder();
for (String s: strs) {
result.append(s);
}
return result.toString();
}
|
本质上都是使用了排序（字典序）
