31 把数组排成最小的数 + 仿函数的写法就记忆这个就行了

题目描述

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

 

 

思路：

1）使用permutation全排列的思路，和字符串全排列很像，只不过需要处理压入之后弹出的操作，以及压入结果的判断条件。

记住字符串操作string类型可以直接进行相加，比如a + b = ab；不需要考虑a的结束符号，而且size不包含最后的结束符号。

class Solution {
public:
    void helper(vector<int> &numbers,vector<bool> &visit,string &tmp,string &result,int flag){
        if(flag == tmp.size()){
            if(tmp < result){
                result = tmp;
            }
        }
        for(int i = 0;i < numbers.size();++i){
            if(i != 0 && numbers[i] == numbers[i - 1] && visit[i - 1] == false || visit[i] == true){
                continue;
            }
            visit[i] = true;           
            string i2str =  to_string(numbers[i]);
            int len = i2str.size();
            tmp += i2str;
            helper(numbers,visit,tmp,result,flag);
            while(len-- > 0){
                tmp.pop_back();
            }           
            visit[i] = false;
        }
    }
    string PrintMinNumber(vector<int> numbers) {
        if(numbers.empty()){
            return "";
        }       
        int sz = numbers.size();
        string test;
        for(int num : numbers){
            test += to_string(num);
        }
        vector<bool> visit(sz,false);
        string tmp;       
        string result(11,'9');
        helper(numbers,visit,tmp,result,test.size());
        return result;
    }
};

2）定制比较函数版本。

sort的定制函数写法是：

方法1：声明外部比较函数

比较函数必须写在类外部（全局区域）或声明为静态函数，static可以在函数的全局用，传进去的less是一个函数指针，所以直接可以调用less。

（当comp作为类的成员函数时，默认拥有一个this指针，这样和sort函数所需要使用的排序函数类型不一样。）

static bool Less(const Student& s1, const Student& s2){  
    return s1.name < s2.name; //从小到大排序  
}  
std::sort(sutVector.begin(), stuVector.end(), Less);  

方法2：重载类的比较运算符//这个放在类里面，如果是内置类型就可以直接写在程序中。

bool operator<(const Student& s1, const Student& s2) {  
    return s1.name < s2.name; //从小到大排序  
}  
std::sort(sutVector.begin(), stuVector.end());  

方法3：声明比较类，传入的部分是个对象，()也是一个对象，也可以写cmp  a，然后传入一个a。内部的sort第三个参数猜测是一个引用，这样就可以调用这个对象的operator方法。

struct Less{  
    bool operator()(const Student& s1, const Student& s2)  
    {  
        return s1.name < s2.name; //从小到大排序  
    }  
};    
std::sort(sutVector.begin(), stuVector.end(), Less()); 

class Solution {
public:
    struct cmp{
        bool operator()(const string &lhs,const string &rhs){        
            string a = lhs + rhs;
            string b = rhs + lhs;
            return a < b;
        }
     };
    bool cmp1(const string &lhs,const string &rhs){
        string a = lhs + rhs;
            string b = rhs + lhs;
            return a < b;
    }
    string PrintMinNumber(vector<int> numbers) {
        if(numbers.empty()){
            return "";
        }
        vector<string> str;
        for(int num : numbers){
            str.push_back(to_string(num));
        }
        string res;        
        sort(str.begin(),str.end(),cmp());//cmp ()创建一个空对象，这样里面才可以调用
        for(string tmp : str){
            res.append(tmp);
        }
        return res;
    }
};