面试题45(Java)-把数组排成最小的数（中等）

题目：

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]

输出: "102"

示例 2:

输入: [3,30,34,5,9]

输出: "3033459"

提示:

• 0 < nums.length <= 100

说明:

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

 详情解释：可以看 K神老师以及评论区的题解

图片来源于 @K神老师

 思路：

①首先将数组转换成字符串列表；

②基于快速排序的排序规则，对字符列表进行排序；

③拼接排序后的字符串，返回结果即可。

 推荐看一下：博主codereasy的视频，看他的动画讲解的很清楚，然后再看代码就很好理解啦！

代码：

 1 class Solution {
 2     public String minNumber(int[] nums) {
 3        //将数组转换成字符串列表
 4        String[] strs = new String[nums.length];
 5        for(int i = 0; i < nums.length; i++){
 6            strs[i] = String.valueOf(nums[i]);
 7        }
 8        //将字符串列表进行快速排序
 9        quickSort(strs, 0, strs.length-1);
10        //将排序好的结果进行拼接并输出
11        StringBuffer sb = new StringBuffer();
12        for (String s: strs){
13            sb.append(s);
14        }
15        return sb.toString();
16     }
17        //定义快速排序方法
18     public void quickSort(String[] strs, int start, int end){
19         if (start < end){
20             //一轮排序后获取的中间位置
21             int middle = getMiddle(strs, start, end);
22             //这时候基准位置的左边都比它小，右边都比它大
23             //快排基准位置左边部分
24             quickSort(strs, start, middle - 1);
25             //快排基准位置右边的部分
26             quickSort(strs, middle + 1, end);
27         }
28     }
29     public int getMiddle(String[] strs, int left, int right){
30         //设置基准位置为第一个元素
31         String pivot = strs[left];
32         while(left < right){
33             //从右往左看
34             //小于等于0，代表式子中前面小于等于后面的，于是不交换
35             while(left < right && (pivot + strs[right]).compareTo(strs[right] + pivot) <= 0){
36                 right--;
37             }
38             //上面循环不满足，代表需要移动后面的元素到前面
39             strs[left] = strs[right];
40             //从左往右看
41             while(left < right && (strs[left] + pivot).compareTo(pivot + strs[left]) <= 0){
42                 left++;
43             }
44             //上面循环不满足，代表需要移动前面的元素到后面
45             strs[right] = strs[left];
46         }
47         //left = right,中间位置
48         //把基准元素放在这时的中间
49         strs[left] = pivot;
50         return left;
51     }
52 }

小知识：

compareTo：

str1.compareTo(str2)：如果str1 < str2,就会返回负数，大于就会返回正数，等于返回0。