把数组排成最小的数

知识点 数组 贪心 排序

描述

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

例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。

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

数据范围:

0<=len(numbers)<=100

        刚拿到这道题，感觉完全没有思路。后面 想到可以对数组中的数字按照某种规则排序，拍完序之后的数据连起来就是要求的结果。

        那么问题来了，

        1、数组中的元素要按照什么规则排序才能保证拍好序之后的数组中前一个数据拼接后一个数据比后一个数据拼接前一个数据小呢？

        2、假设已经对原始数组中前n个数据拍好序了，如何找到当前正在遍历的数据应该插入已排好序数组的位置呢？

解决办法：

        第二个问题好解决，利用一个List来存放排好序的数据，利用List可以方便地前插和后插数据，能够满足我们的要求。

        第一个问题是关键，如何比较两个字符串是题目要求那样的呢？ 首先想到的是否能直接利用字符串String本身的比较函数compareTo()方法呢？通过查看String#compareTo()发现它先比较两个字符串相同长度部分，如果相同长度部分能比较大小则返回结果，如果相同部分比较不出，则根据字符串长度来比较大小。不太符合我需要的规则，比如32 ，321这两个数，如果用String的compareTo()比较，321>32，但我们想要的结果是321 < 32。

        接下来就是寻找一种合适的比较规则能符合题目要求。这时我们可以通过列举几个数据来寻找规律：

        第一组：32 3

        第二组：1234 12341 12342 123412

第一组很好比较，3 32 > 32 3，所以f(3)>f(32)。

第二组：第二组我们发现我们可以通过这样的规则比较大小，假设一个字符串长，一个字符串短，则用短的去遍历长字符串中具体相同长度的子字符串，直到比较到长字符串剩余的字符长度小于短字符串长度时。如果能比较出大小，则返回结果。如果比较不出结果，则比较长字符串中剩余的子字符串和短字符串的大小，然后返回结果。

比如1234和123412进行比较，首先比较长度相同部分，1234和1234相等；再比较长字符串剩余部分和短字符串， 12和1234比较，f(12)<f(1234)。

--- 算了， 发现这里逻辑有点混乱，虽然牛客网上答案通过了，但是后面发现是错的，比如654365和6543这个程序就会出错。

虽然是错误代码，还是先粘贴一下，后面再修正吧

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        if (numbers == null || numbers.length == 0) {
            return "";
        }
        String minStr = "";
        int length = numbers.length;
        
        //借助一个List来前插或后插数据，保存的是排序好的数据集合，把它串起来就是我们想要的数据
        //每遍历到数组一个数据，就和list中从前到后每个数据进行比较，判断该数据应该插入的位置
        //对于位数不同的两个数字，更长的数字先取出和短数字一样长的子数字比较，如果一样大，
        //则长数据继续取剩余的数据和短数据比较，直到比较出大小为止
        List<String> list = new ArrayList<String>();
        list.add(String.valueOf(numbers[0]));
        for (int i = 1; i < length; i++) {
            String str = String.valueOf(numbers[i]);
            boolean inserted = false;
            int listSize = list.size();
            for (int j = 0; j < listSize; j++) {     
                if (!compare(str, list.get(j))) {
                //if (!compare2(str, list.get(j))) {
                    inserted = true;
                    list.add(j, str);
                    break;
                }
            }
            if (!inserted) {
                list.add(str);
            }
        }
        StringBuilder builder = new StringBuilder("");
        for (String s : list) {
            builder.append(s);
        }
        minStr = builder.toString();
        return minStr;
    }
    
    public boolean compare(String str1, String str2) {
        String strMax = "";
        String strMin = "";
        //自己实现的比较算法
        int length1 = str1.length();
        int length2 = str2.length();
        int flag = 1;
        if (length1 >= length2) {
            strMax = str1;
            strMin = str2;
            flag = 1;
        } else {
            strMax = str2;
            strMin = str1;
            flag = 2;
        }
        int lengthMin = strMin.length();
        int count = 0;
        int compareRes = Integer.MAX_VALUE;
        while (count * lengthMin + lengthMin  <= strMax.length()) {
            String subStr = strMax.substring(count * lengthMin,
                                             count * lengthMin + lengthMin);
            compareRes = subStr.compareTo(strMin);
            if (compareRes > 0) {
                if (flag == 1) {
                    return true;
                } else {
                    return false;
                }
            } else if (compareRes < 0) {
                if (flag == 1) {
                    return false;
                } else {
                    return true;
                }
            }
            count++;
        }
        if (count * lengthMin + lengthMin > strMax.length()) {
            compareRes = strMax.substring(count * lengthMin,strMax.length())
                .compareTo(strMin);
            if (compareRes > 0) {
                if (flag == 1) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        return false;
    }
}

在看过正确答案之后，发现比较两个字符串有一种非常简单又非常好理解的方法，就是把两个字符串正序和反序拼接一下，比较这两个字符串大小即可，这时候完全可以用String自带的比较方法compareTo()了。因为正序和反序拼接字符串之后，两个字符串的长度一致，直接可以String自带的比较方法。不用像我上面比较起来那么麻烦了。

    public boolean compare2(String str1, String str2) {
        if ((str1 + str2).compareTo(str2 + str1) >= 0) {
            return true;
        }
        return false;
    }

这个是真的简单且好理解！！

 下面贴出大神的解法，简直吊炸天！！

思路 & 解答

这道题要求拼起来的数是最小的数字，其实是一个排序问题，只要理解了这一点，就可以快速解决。 假设有两个字符串s1=3，s2=32，那s1+s2=332,s2+s1=323,也就是s1+s2>s2+s1。 像上面这种情况，要想拼接起来的数最小，肯定是s2在前面，s1在后面。

而在数组中，我们要使所有的拼接起来是最小，则需要两两比较，类似排序，把满足s1+s2>s2+s1的s1放到后面，s2放到前面。

而排序算法有很多种，我们直接调用API的，如果使用冒泡就是O(n2),内置的函数是O(NlogN)，最差的时候是O(n2)。

代码如下：

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        String[] strs = new String[numbers.length];
        for(int i = 0; i < numbers.length; i++) 
            strs[i] = String.valueOf(numbers[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
}

当然，要是自己实现排序算法也是完全ok的。

参考文章：https://github.com/Damaer/CodeSolution/blob/main/%E5%89%91%E6%8C%87Offer/%E5%89%91%E6%8C%87Offer32-%E6%8A%8A%E6%95%B0%E7%BB%84%E6%8E%92%E6%88%90%E6%9C%80%E5%B0%8F%E7%9A%84%E6%95%B0.md