【算法刷题题解】面试题45 把数组排成最小的数

比眉伴天荒 2023-09-27 17:06 32阅读 0赞

**目录**

题目描述

题解思路

题解代码

--------------------

## 题目描述 ##

**力扣算法题：把数组排成最小的树， 难度：中等**

力扣题目链接：[把数组排成最小的数][Link 1]

> 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
> 
> 测试用例：
> 
>     输入1: [10,2]
>     
>     输出1: "102"
> 
>     输入2: [3,30,34,5,9]
>     
>     输出2: "3033459"

--------------------

## 题解思路 ##

1、采用冒泡排序思想，其他排序方法也可以

2、将数组第一位和第二位按照 "**第一位+""+第二位**" 拼接或者"**第二位+""+第一位**"拼接

3、用**字典序(compareTo)**进行比较大小，**若前者大于后者，字典序结果则为大于0** ，采取后者的拼接组合（即使用小的拼接组合）

4、依次进行后续数组元素字典序比较

5、最后用新字符串接收并返回

--------------------

## 题解代码 ##

class Solution {
        public String minNumber(int[] nums) {
            /**
            1、采用冒泡排序思想，其他快速排序也可以
            2、将数组第一位和第二位按照  "第一位+""+第二位" 拼接或者"第二位+""+第一位"拼接
            3、用字典序进行比较大小，采取小的拼接组合
            4、依次进行后续字典序比较
            5、最后用新字符串接收并打印输出
             */
             for(int i=0;i<nums.length-1;i++){//冒泡排序
                for(int j=0;j<nums.length-1-i;j++){
                      String s1 = nums[j] + "" +nums[j+1];//字符串拼接
                      String s2 = nums[j+1] + "" +nums[j];
                      if(s1.compareTo(s2)>0){//字典序比较
                          int tmp=nums[j];
                          nums[j]=nums[j+1];
                          nums[j+1]=tmp;
                        }
                    }
               }
         StringBuilder str = new StringBuilder();
            for(int i=0;i<nums.length;i++){
                str.append(nums[i]);
            }
            return str.toString();
        }
    }

[Link 1]: https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/