把数组排成最小的数

题目的主要信息：

• 有一个数字中全部都是非负整数
• 将其随意拼接后要使拼接后的数字整体最小
• 返回这个最小数字的字符串形式

举一反三：

学习完本题的思路你可以解决如下题目：

JZ41. 数据流中的中位数

方法一：重载比较的排序（推荐使用）

知识点：排序

排序就是将一个线性数据的元素按照一定的次序进行重排，这个次序可能是递增序、也可能是递减序，还有可能是自己定义的顺序（重载），常用的方法一般有快速排序、堆排序、归并排序、冒泡排序、选择排序等。再程序中的可以使用sort函数，它是基于优化后的快速排序。

思路：

这道题呢最重要的解决怎么样组装的数字是最小的，按照什么顺序组装？如果我们能得到这个次序，直接将这个次序的数字拼接在一起就好了。

只考虑首字符的大小不可靠，但是如果字符串a拼接b的得到的数字大于b拼接a，那么肯定b应该排在a的前面，我们要就按照这样的次序将排序的比较重载就可以了。

bool cmp(string& x, string& y){
    //叠加
    return x + y < y + x;
}

具体做法：

• step 1：优先判断空数组的特殊情况。
• step 2：将数组中的数字元素转换成字符串类型。
• step 3：重载排序比较为字符串类型的x + y < y + x，然后进行排序。
• step 4：将排序结果再按照字符串拼接成一个整体。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        //空数组的情况
        if(numbers == null || numbers.length == 0)
            return "";
        String[] nums = new String[numbers.length];
        //将数字转成字符
        for(int i = 0; i < numbers.length; i++)
            nums[i] = numbers[i] + "";
        //按照重载排序
        Arrays.sort(nums, new Comparator<String>() {
            public int compare(String s1, String s2) {
                return (s1 + s2).compareTo(s2 + s1);
            }
        });
        StringBuilder res = new StringBuilder();
        //字符串叠加
        for(int i = 0; i < nums.length; i++)
            res.append(nums[i]);
        return res.toString();
    }
}

C++实现代码：

class Solution {
public:
    //重载排序比较方式
    static bool cmp(string& x, string& y){
        //叠加
        return x + y < y + x;
    }
    string PrintMinNumber(vector<int> numbers) {
        string res = "";
        //空数组的情况
        if(numbers.size() == 0)
            return res;
        vector<string> nums;
        //将数字转成字符
        for(int i = 0; i < numbers.size(); i++)
            nums.push_back(to_string(numbers[i]));
        //排序
        sort(nums.begin(), nums.end(), cmp);
        //字符串叠加
        for(int i = 0; i < nums.size(); i++)
            res += nums[i];
        return res;
    }
};

Python实现代码：

import functools
class Solution:
    def PrintMinNumber(self , numbers: List[int]) -> str:
        #空数组的情况
        if not numbers:
            return ""
        #将数字转成字符
        nums = list(map(str, numbers))
        #重载比较大小
        cmp = lambda a, b: 1 if a + b > b + a else -1
        #排序
        nums.sort(key = functools.cmp_to_key(cmp))
        #字符串叠加
        return "".join(nums)

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，其中$nn$为数组的长度，遍历两次数组，最坏复杂度为排序
• 空间复杂度：$O(n)O(n)$，利用辅助数组存储字符串类型的数字

方法二：冒泡排序（扩展思路）

思路：

如果觉得重载比较的方式自己掌握不太熟练，那我们可以直接尝试冒泡排序，冒泡排序过程要求比较数组相邻位置元素的大小，我们可以改成比较数组相邻字符串拼接之后的大小。

具体做法：

• step 1：优先判断空数组的特殊情况。
• step 2：将数组中的数字元素转换成字符串类型。
• step 3：使用冒泡排序，两层遍历数组，每次比较数组相邻位置字符串拼接的大小，如果顺序拼接比逆序拼接更大，则需要交换位置。
• step 4：将排序结果再按照字符串拼接成一个整体。

Java实现代码：

import java.util.*;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        //空数组的情况
        if(numbers == null || numbers.length == 0)
            return "";
        String[] nums = new String[numbers.length];
        //将数字转成字符
        for(int i = 0; i < numbers.length; i++)
            nums[i] = numbers[i] + "";
        //冒泡排序
        for(int i = 0; i < nums.length - 1; i++){
            for(int j = 0; j < nums.length - i - 1; j++){
                String s1 = nums[j] + nums[j + 1];
                String s2 = nums[j + 1] + nums[j];
                //比较拼接的大小交换位置
                if(s1.compareTo(s2) > 0){
                    String temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        StringBuilder res = new StringBuilder();
        //字符串叠加
        for(int i = 0; i < nums.length; i++)
            res.append(nums[i]);
        return res.toString();
    }
}

C++实现代码：

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        string res = "";
        //空数组的情况
        if(numbers.size() == 0)
            return res;
        vector<string> nums;
        //将数字转成字符
        for(int i = 0; i < numbers.size(); i++)
            nums.push_back(to_string(numbers[i]));
        //冒泡排序
        for(int i = 0; i < nums.size() - 1; i++){
            for(int j = 0; j < nums.size() - i - 1; j++){
                string s1 = nums[j] + nums[j + 1];
                string s2 = nums[j + 1] + nums[j];
                //比较拼接的大小交换位置
                if(s1 > s2)
                    swap(nums[j], nums[j + 1]);
            }
        }
        //字符串叠加
        for(int i = 0; i < nums.size(); i++)
            res += nums[i];
        return res;
    }
};

Python实现代码：

class Solution:
    def PrintMinNumber(self , numbers: List[int]) -> str:
        #空数组的情况
        if not numbers:
            return ""
        #将数字转成字符
        nums = list(map(str, numbers))
        #冒泡排序
        for i in range(len(nums) - 1):
            for j in range(len(nums) - i - 1):
                s1 = nums[j] + nums[j + 1]
                s2 = nums[j + 1] + nums[j]
                #比较拼接的大小交换位置
                if s1 > s2:
                    temp = nums[j]
                    nums[j] = nums[j + 1]
                    nums[j + 1] = temp
        #字符串叠加
        return "".join(nums)

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，其中$nn$为数组的长度，冒泡排序最坏遍历两层数组
• 空间复杂度：$O(n)O(n)$，利用辅助数组存储字符串类型的数字