题解 | #把数组排成最小的数#

题目：把数组排成最小的数

描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

示例1：输入：[3,32,321]，返回值："321323"。

思路分析：例题中给了三个数的集合，我们首先分析两个数的情况[3,32]，通过分析，可以得到332>323，因此可以将数组改变为按大小排序[32,3]，当存在三个数的时候，我们进行分析三个数的情况：

[3,32,321]

首先进行两两之间的配对，因为332>323，所以将3与32交换位置变成：

[32,3,321]

由于3321>3213，于是将3与321继续交换位置得到：

[32,321,3]

由于32321>32132，所以将32与321进行位置交换得到：

[321,32,3]

此时，将数组连接起来，就变成为了最小数为321323

具体思路分析：首先将数字列表转化为字符串链表，这样就可以直接将字符串添加到另一个字符串后边，方便。其次应该构造一个比较函数当str1+str2>str2+str1时，我们就认为str1>str2str1>str2。将字符串列表按照规定进行排序，将大的字符放到最后，将小的字符放到前面，最后将所有的字符串连接起来，便是要求所得到的最小值。

具体C++代码如下所示：

class Solution {
public:
    string PrintMinNumber(vectornumbers) {
        vectorstr;
        for(int val : numbers)
            str.push_back(to_string(val));
        sort(str.begin(), str.end(),com);
        string ver = "";
        for(string s : str)
            ver += s;
        return ver;
    }
    bool static com(string a, string b) {
        return a + b < b + a; } };

其中时间复杂度为O(NlogN)，空间复杂度为O(N)

解法二：

思路分析：同样也可以直接采用暴力法，将数组中元素的所有排列情况放入list中，然后根据list当中的字符串的排序情况输出最小的排列即可。

具体实例分析：

其java代码为：

import java.util.ArrayList;
import java.util.*;
 
public class Solution {
    ArrayList<String> list = new ArrayList<>();//创建一个新的链表
    String str="";
    public String PrintMinNumber(int [] numbers) {
        if(numbers.length == 0)
            return str;
        getpermutation(numbers,0,numbers.length);
        Collections.sort(list);
        return list.get(0);
    }
    
    public void getpermutation(int[] array, int start, int end){
        if(end < 0)
            return ;
        if(start == end){
            Str(array);
    }
        else{
            for(int i = start;i < end;i++){
                swap(array,i,start);
                getpermutation(array,start + 1,end);
                swap(array,start,i);
            }
        }
    }
    
    public void swap(int[] array, int i, int j){
        int ch = array[i];
        array[i] = array[j];
        array[j] = ch;
  }
    public void Str(int[] array){
        String str = "";
        for(int i = 0;i < array.length;i++)
            str = str + Integer.valueOf(array[i]);
        if(!list.contains(str))
            list.add(str);
    }
}