数据结构学习 jz45 把数组排成最小的数

关键词：贪心 排序 快速排序

题目：破解闯关密码

思路：

快排+自己制定快排规则

开辟一个vector存string，自己制定排序规则，然后用快排比较string大小。

排序规则：

sort(strs.begin(),strs.end(),[](string& a,string& b){return a+b<b+a;});

?复杂度计算：

时间复杂度O(nlogn)

空间复杂度O(n) //字符串vector

代码：

class Solution {
public:
    string crackPassword(vector<int>& password) {
        vector<string> strs;
        string res;
        for(int i=0;i<password.size();++i)
        {
            strs.push_back(to_string(password[i]));
        }
        sort(strs.begin(),strs.end(),[](string& a,string& b){return a+b<b+a;});
        for(int i=0;i<strs.size();++i)
        {
            res.append(strs[i]);
        }
        return res;
    }
};