题目陈述

大意：给定一个数组，，将数组凭借成一个字符串，使得字符串的字典序最小

算法1：朴素做法

算法思路

显然，n个数排序有 $A^n_n=n!$ 种序列
最朴素的做法，我们在这 $n!$ 种排序中，每个都拼接成字符串，依次比较，记录最小的即可
当然，这个算法的重点的是如何生成一个数组的全排序
方法1：递归生成全排序
这边简单提一下（重点还是方法2），方法1大家知道一下就行了
注意：这边的a数组从小到大排序过的
只需要对于第h层,只需要让他跟[h,len-1]中的数，一次交换，就可以依次得到，从小到大的序列
感性理解一下，同一层for循环总（即同一层h中），先交换的字典序一定是比后交换的小，这样就能保证我们得到的序列的字典序大小是递增的
我们进行搜索，当h=len-1时候，即到达递归边界的时候，我们放入vector<vector<int> > All_per中,

最后我们在这个vector中再拼接，得到最小的那个字符串即可

代码实现

int len=a.size();
void dfs(int h){
  if(h==len-1){//得到一次排列
      All_per.push_back(a);//放入vector<vector<int> >中
  }
  for(int i=h;i<len;i++){
      swap(a[i],a[h]);
      dfs(h+1);
      swap(a[i],a[h]);//还原
  }
}

动画演示

方法2：库函数生成全排序

借助C++自带的库函数next_permutation，我们便可以得到比当前序列大的第一个序列
此处依旧需要先排序，先从字典序最小的开始，依次增大，然后便可以遍历所有的排序

注意，如果当前序列是最大的字典序（即没有下一个字典序），那么next_permutation（）返回的是false，否则返回yes

class Solution {
public:
  string PrintMinNumber(vector<int> numbers) {
      vector<string> s;
      string now;
      string ans(numbers.size(),'9');//numbers.size个9，即最大字典序，min的时候
      for(int i=0;i<numbers.size();i++){//将数组转换成字符串，放进vector中
          s.push_back(to_string(numbers[i]));//to_string为C++11新特性，如果用DevC++,命令记得加上-std=c++11
      }
      sort(s.begin(),s.end());//排序后生成最小字典序     
      do{
          now="";//初值设置为空串
          for(string s1:s){//C++11新特性,for(元素 i:容器)
              now+=s1;//拼接新的字符串
          }
          ans=min(now,ans);//更新答案
      }while(next_permutation(s.begin(),s.end()));//当没有下一个字典序的时候(即最大)，返回false
      return ans;
  }
};

复杂度分析

时间复杂度 $O(n \times n!)$ ，拼接的时间为n，生成全排序的时间复杂度为n！
空间复杂度为O(n)，定义了一个vector<string> s;

算法2：贪心+排序

算法思路

我们假设已经知道了，生成最小字典序的序列，那么他们可能有什么性质呢？
抱着这个猜想，我们不妨试一试直接通过答案的性质来生成这个数组
显然，对于答案的，任意两个字符串a,b都有a+b<b+a，此处<为字符串比较大小，如何证明这个性质的正确性呢？
反证法，假设有两个字符串不满足，那么我们交换一下这两个字符串，不就得到了更小的字符串了吗？矛盾，故不存在
既然我们知道了他的排序性质，我们就可以利用强大的sort函数进行排序（pascal选手想可以手写快排也行）
具体实现

1. int转为string方式

C++
借助C++11新特性的to_string函数，我们可以直接写to_string(numbers[i]来完成
python
python可以借助map()来完成int转string,即a=list(map(str,numbers))
2. 排序方式
此处排序有多种方法，看自己喜欢用哪个，个人习惯lambda表达式
i. 仿函数
给小白们补充一个知识，什么是仿函数，也叫做仿函数类，（因为C++里面class和struct几乎可以互相替代了）

表面上他是一个类，但是实际上他只起到一个重载运算符的作用，所以称之为仿函数

struct Cmp{//仿函数，重载"()"运算符，叫做“函数调用符”
  bool operator()(string a,string b){
      return a+b<b+a;
  }
};
class Solution {
public:
  string PrintMinNumber(vector<int> numbers) {
      vector<string> s;
       for(int i=0;i<numbers.size();i++){//将数组转换成字符串，放进vector中
          s.push_back(to_string(numbers[i]));//to_string为C++11新特性，如果用DevC++,命令记得加上-std=c++11
      }
      sort(s.begin(),s.end(),Cmp());//记得Cmp后面有一个“()”  
      string ans;
      for(string s1:s)ans+=s1; //C++11新特性,for(元素 i:容器)，拼接答案
      return ans;
  }
};

ii. 类中static函数

因为sort中的参数，不能直接调用类的函数

如果直接用this指针会报错，所以需要变成静态的，即static,就可以不用this指针调用了，这样就不会报错了

class Solution {
public:
  bool static cmp(string a,string b){//排序规则
      return a+b<b+a;
  }
  string PrintMinNumber(vector<int> numbers) {
      vector<string> s;
       for(int i=0;i<numbers.size();i++){//将数组转换成字符串，放进vector中
          s.push_back(to_string(numbers[i]));//to_string为C++11新特性，如果用DevC++,命令记得加上-std=c++11
      }     
      sort(s.begin(),s.end(),cmp);      
      string ans;
      for(string s1:s)ans+=s1; //拼接答案
      return ans;
  }
};

iii.lambda表达式

每次是不是还在为想一个函数名而头疼？那么你可以用lambda表达式，他的好处之一，就是可以不用函数名
其中[&]表示引用传递方式捕捉所有父作用域的变量(包括this)
当然也可以利用C++11的auto新特性，（因为编译器会帮你自动识别），当然这个貌似用的比较少（据说不规范）

下面给出C++的匿名lambda表达式和Python的具名lambda表达式的代码

C++

class Solution {
public:
  string PrintMinNumber(vector<int> numbers) {
      vector<string> s;
       for(int i=0;i<numbers.size();i++){//将数组转换成字符串，放进vector中
          s.push_back(to_string(numbers[i]));//to_string为C++11新特性，如果用DevC++,命令记得加上-std=c++11
      }
      sort(s.begin(),s.end(),[&](string a,string b){return a+b<b+a;}); //排序 
      //匿名lambda表达式
      //[&]表示引用传递方式捕捉所有父作用域的变量(包括this) 
      string ans;
      for(string s1:s)ans+=s1; //拼接答案
      return ans;
  }
};

Python2

此处要注意的是Python2中可以直接调用sort(cmp)来实现，但是Pyhon3中cmp这个参数被取消了，只能借助functools中的cmp_to_key函数来实现

class Solution:    
     def PrintMinNumber(self, numbers):
      a=list(map(str,numbers))#将数字转换为字符串，储存在列表用
      comp=lambda a,b:1 if a+b>b+a else -1#具名lambda表达式
      a.sort(cmp=comp)#排序
      return "".join(a)#将列表内的各个元素连接起来

Python3

class Solution:    
     def PrintMinNumber(self, numbers):
      import functools #python3中sort的cmp参数被取消了，只能调用这个库来实现
      a=list(map(str,numbers))#将数字转换为字符串，储存在列表用
      cmp=lambda a,b:1 if a+b>b+a else -1#具名lambda表达式
      a.sort(key=functools.cmp_to_key(cmp))#调用cmp_to_key实现排序
      return "".join(a)#将列表内的各个元素连接起来

3. 复杂度分析

排序时间复杂度为 $O(n \log n)$ ,拼接为 $O(n)$ ,总的为 $O(n \log n)$ ，这边有同学好奇为什么不写作 $O(n+n \log n )$
我们复杂度分析，分析的是最高阶的，或者说n很大的时候的极限
就比如有一个n方的for循环，那这个时候其余的一层的for循环我们就会忽略掉，分析复杂度默认n趋于很大的数（无穷大），如 $\lim_{x \to +\infty} \cfrac{n^2+3n+3}{n^2}=1$
所以一般情况我们只写最高的阶，即 $O(n\log n)$

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

题目陈述

算法1：朴素做法

算法思路

方法1： 递归生成全排序

代码实现

动画演示

方法2：库函数生成全排序

复杂度分析

算法2：贪心+排序

算法思路

具体实现

1. int转为string方式

C++

python

2. 排序方式

i. 仿函数

ii. 类中static函数

iii.lambda表达式

C++

Python2

Python3

3. 复杂度分析

方法1：递归生成全排序