作者:whisper
链接:https://www.proprogrammar.com/article/901
声明:请尊重原作者的劳动,如需转载请注明出处
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2] 输出: "102"
示例 2:
输入: [3,30,34,5,9] 输出: "3033459"
提示:
0 < nums.length <= 100
说明:
- 输出结果可能非常大,所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
难度:中等;标签:排序;编程语言:JAVA
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]);
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
这题做了一点印象都没有,解法完全忘了,复习一下,数字转成字符串,字符串比较大小(连接后按ASCII码来排序),如201和20,20201大于20120,所以是201在前,20在后(既然结果是一个连接后的字符串,那我们两两连接后比较)
class Solution {
public String minNumber(int[] nums) {
fastSort(nums, 0, nums.length - 1);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < nums.length; i++)
sb.append(nums[i]);
return sb.toString();
}
private int compare(int o1, int o2) {
if (o1 == 0 || o2 == 0)
return o1 == 0 ? -1 : 1;
return and(o1, o2) > and(o2, o1) ? 1 : -1;
}
private long and(int a, int b) {
int multiplier = 1, tmp = b;
while (tmp > 0) {
tmp /= 10;
multiplier *= 10;
}
return (long)a * multiplier + b;
}
private void fastSort(int[] nums, int l, int r) {
if (r < l) return;
int cur = l - 1;
for (int i = l; i < r; i++) {
// 记录符合‘小于’的位置
if (compare(nums[i], nums[r]) >= 0 || ++cur == i)
continue;
// 将第一个不符合‘小于’的位置与当前符合‘小于’的位置交换
swap(nums, cur, i);
}
if (++cur != r)
swap(nums, cur, r);
fastSort(nums, l, cur - 1);
fastSort(nums, cur + 1, r);
}
private void swap(int[] nums, int n, int m) {
nums[n] ^= nums[m];
nums[m] ^= nums[n];
nums[n] ^= nums[m];
}
}
与解法1方法一样,不同的是自己写了一个快速排序的方法
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202205 | 1 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论