2021/3/16 剑指 Offer 45. 把数组排成最小的数

题目描述

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

示例1

输入: [10,2]
输出: "102"

示例2

输入: [3,30,34,5,9]
输出: "3033459"

解题思路

1. 用上面示例 2 进行举例。将两个相邻的数字加起来，再互换一下位置继续比较。如 "3" 和 "30" 组成 330，"30" 和 "3" 组成 303，发现 303 < 330，所以把数组中 3 与 30 的位置互换一下。
2. 进行冒泡排序，最终排列出一个最小的数值。

Java代码实现

class Solution {
    public String minNumber(int[] nums) {
        for (int i = 0; i < nums.length - 1; ++i) {
            for (int j = 0; j < nums.length - i - 1; ++j) {
                String temp1 = String.valueOf(nums[j]);
                String temp2 = String.valueOf(nums[j + 1]);
                long nums1 = Long.parseLong(temp1 + temp2);    // 3 30
                long nums2 = Long.parseLong(temp2 + temp1);    // 30 3
                if (nums1 > nums2) {
                    int temp = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        // 拼接
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < nums.length; ++i) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }
}