描述

这是一篇针对初学者的题解，共用2种方法解决。
知识点：数组，全排列，排序，贪心
难度：一星

题解

题目抽象：给一个包含n个整数的vector，将n个整数组成一个最小的字符串。

方法一：暴力方法

假设n个整数的索引为[0...n-1]，如果我们对这n个索引进行全排列，然后再对每次全排列进行组织一下结果，选取最小的即为答案。比如[1, 2, 3] 的全排列为：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

全排列的代码为：

void perm(int pos, vector<int> &num, vector<vector<int>> &all_result) {
    if (pos + 1 == num.size()) {
        // 一次全排列的结果
        all_result.push_back(num);
        return;
    }
    for (int i = pos; i < num.size(); ++i) {
        swap(num[pos], num[i]);
        perm(pos+1, num, all_result);
        swap(num[pos], num[i]);
    }
}
int main() {
    vector<int> num = {1, 2, 3};
    vector<vector<int>> all_result;
    perm(0, num, all_result);
}

然后将上述代码加以改编，如下：

class Solution {
public:
    void perm(int pos, vector<int> &num, string &ret) {
        if (pos + 1 == num.size()) {
            // 一次全排列的结果
            string tmp = "";
            for (int val : num) {
                tmp += to_string(val);
            }
            ret = min(ret, tmp);
            return;
        }
        for (int i = pos; i < num.size(); ++i) {
            swap(num[pos], num[i]);
            perm(pos+1, num, ret);
            swap(num[pos], num[i]);
        }
    }
    string PrintMinNumber(vector<int> nums) {
        string ret(nums.size(), '9'); // nums.size()个'9'
        perm(0, nums, ret);
        return ret;
    }
};

时间复杂度：O(N*N!),全排列的时间复杂度为N！，每次排列结果需要遍历一次nums数组
空间复杂度：O(1)

拓展：

上述的全排列是自己写的，其实STL中有全排列的库函数std::next_permutation(first, last)。
示例代码如下：

#include <algorithm>
#include <string>
#include <iostream>

int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
}
/*
output:
aab
aba
baa
*/

使用库函数的本题代码：

class Solution {
public:
    string PrintMinNumber(vector<int> nums) {
        vector<string> str;
        for (int val : nums) {
            str.push_back(to_string(val));
        }   
        sort(str.begin(), str.end());
        string ret(nums.size(), '9');
        do {
            string tmp = "";
            for (string val : str)
                tmp += val;
            ret = min(ret, tmp);
        } while (next_permutation(str.begin(), str.end()));
        return ret;
    }
};

方法二：贪心，自定义排序

显然方法一出现了太多无关的排列，我们需要一个最小的数，细想一下可知，如果有两个字符串a,b，
如果a + b < b + a, 显然我们希望a排在b的前面，因为a排在前面可以使结果更小。于是我们就自定义排序规则，使得vector中字符串都满足如上规则，那么最后的结果肯定是最小的。
算法步骤：

1. 将vector<int> 转化为vector<string>
2. 自定义上述排序规则
3. 整合结果

对于第二步的排序规则，实现上，可以用仿函数，lambda表达式，函数指针，针对本题的实现分别如下：

1. 仿函数

   struct Com {
       bool operator() (string a, string b) {
        return a + b < b + a;
       }
   };
   sort(str.begin(), str.end(), Com()); // Com()为临时对象

2. lambda表达式

   // 1. 匿名lambda表达式
   sort(str.begin(), str.end(), [](string a, string b) {
        return a + b < b + a;
   });
   // 2.具名lambda表达式
   auto lam = [](string a, string b) {
        return a + b < b + a;
    };
   sort(str.begin(), str.end(), lam);;

3. 函数指针

bool static com(string a, string b) {
    return a + b < b + a;
}
//加static的原因：类成员函数有隐藏的this指针,static 可以去this指针
sort(str.begin(), str.end(), com);

最后的代码为：

class Solution {
public:
    string PrintMinNumber(vector<int> nums) {
        vector<string> str;
        for (int val : nums) str.push_back(to_string(val));
        sort(str.begin(), str.end(), [](string a, string b) {
            return a + b < b + a;
        });
        string ret = "";
        for (string s : str) ret += s;
        return ret;
    }
};

时间复杂度：O(NlogN), 采用了排序
空间复杂度：O(N)