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

题目链接

问题描述

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

官方解法

自定义排序规则，对数组中的数字进行排序，当$xy>yx$时，此时$x<y$，按照此规则对数组进行重新排序后，直接遍历有序数组进行添加即可

（官解中直接使用了编程语言的内部实现，在面试时还是推荐手写排序算法）

代码

class Solution {
    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]);
        }
        //直接通过lamda表达式实现排序
        Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));
        StringBuffer res = new StringBuffer();
        for(String s:strs){
            res.append(s);
        } 

        return res.toString();
    }
}

证明

使用上述结论，需要证明以上结论的合理性（遇到变态的面试官可能会问）

字符串 xy < yx , yz < zy ，需证明 xz < zx 一定成立。

设十进制数 x, y, z 分别有 a, b, c 位，则有：
（左边是字符串拼接，右边是十进制数计算，两者等价）
# 确实是相等的 我也不知道为什么...
xy = x * 10^b + y 
yx = y * 10^a + x

则 xy < yx 可转化为：
x * 10^b + y < y * 10^a + x
x (10^b - 1) < y (10^a - 1)
x / (10^a - 1) < y / (10^b - 1)     ①

同理， 可将 yz < zy 转化为：
y / (10^b - 1) < z / (10^c - 1)     ②

将 ① ② 合并，整理得：
x / (10^a - 1) < y / (10^b - 1) < z / (10^c - 1)
x / (10^a - 1) < z / (10^c - 1)
x (10^c - 1) < z (10^a - 1)
x * 10^c + z < z * 10^a + x
∴  可推出 xz < zx ，传递性证毕

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。