剑指 Offer 45: 把数组排成最小的数

[songyy5517]

输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。

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

示例1

输入：[11,3]
返回值："113"

示例2

输入：[]
返回值：""

示例3

输入：[3,32,321]
返回值："321323"

分析 这道题的本质是元素排序。我们需要额外定义元素之间的比较规则：设a, b为两个数字，若字符串ab < ba，则 a < b。然后，我们基于新的比较规则对数组进行排序即可。

[songyy5517]

思路：基于字符串比较的冒泡排序

1. 异常处理；
2. 将整数数组转换成字符串数组；
3. 基于字符串比较对字符串数组进行升序排列；
   • 排列组合当前串和下一个串，拼接得到两个数字字符串，比较两个串大小 （str1.compareTo(str2)）：
     • 若当前串在前的字符串较大，则交换当前串和下一个串的位置；
4. 按从小到大的顺序依次将字符串中的元素拼接起来 （StringBuffer.append()）；
5. 返回结果。（StringBuffer.toString()）

复杂度分析：

• 时间复杂度： $O(N^2)$ ，时间复杂度取决于排序算法，冒泡排序需要 $O(N^2)$ 的时间。
• 空间复杂度： $O(N)$ ，需要额外定义 $O(N)$ 大小的字符串空间来保存所有的数组元素。

[songyy5517]

import java.util.*;
public class Solution {
    public String PrintMinNumber (int[] numbers) {
        // write code here
        // 分析：这道题的本质是数字的组合。最直接的方法是对所有数字进行
        // 全排列，然后选出最小的数字。用新比较规则改进的冒泡排序。

        // 1. 异常处理
        if (numbers == null || numbers.length == 0)
            return new String();

        // 2. 冒泡排序
        for (int i = 0; i < numbers.length; i++){
            for (int j = 0; j < numbers.length - 1 - i; j++){
                String a_str = numbers[j] + "";
                String b_str = numbers[j + 1] + "";

                if ((a_str + b_str).compareTo(b_str + a_str) > 0){
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }

        // 3. 数组转换成字符串
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < numbers.length; i++)
            res.append(numbers[i] + "");

        return res.toString();
    }
}

[songyy5517]

2023/3/6

1. 比较时，不能直接比较两个字符串元素，而应比较他们拼接后的字符串。

2023/5/17

1. 不熟悉str1.compareTo(str2)

2023/11/29 2024/3/6