[数据结构与算法]剑指 Offer 45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"
示例?2:

输入: [3,30,34,5,9]
输出: "3033459"
?

提示:

0 < nums.length <= 100
说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

下面代码220样例，差3个气死了。

class Solution {
public:
    static bool cmp(string a, string b) {
        if (a.length() == b.length()) return a < b;
        bool change = false;
        if (a.length() < b.length()) {
            string t = b;
            b = a;
            a = t;
            change = true;
        }
        bool flag = true; //a<b
        int len =b.length();
        if (a.substr(0, len) == b) {
            int pos = b.length();
            for (int i = pos; i < a.length(); ++i) {
                for (int j = 0; j < b.length(); ++j) {
                    if (a[i] == b[j]) continue;
                    else if (a[i] > b[j]) {
                        flag = false; //a>b
                        break;
                    }
                }
                if (!flag) break;
            }
        }
        else {
            for (int i = 0; i < len; ++i) {
                if (a[i] == b[i]) continue;
                else if (a[i] < b[i]) {
                    if (!change) {return true;}
                    else {return false;}
                }
                else {
                    if (!change) {return false;}
                    else {return true;}
                }
            }
        }
        if ((!change) && flag) return true;
        else if ((!change) && (!flag)) return false;
        else if (change && flag) return false;
        else return true;
    }

    string minNumber(vector<int>& nums) {
        int len = nums.size();
        string ans;
        if (len == 0) return ans;
        vector<string> v;
        for (int i = 0; i < len; ++i) {
            string s = to_string(nums[i]);
            v.push_back(s);
        }
        sort(v.begin(), v.end(), cmp);
        for (int i = 0; i < len; ++i) {
            ans += v[i];
        }
        return ans;
    }
};

另外碰到的大神题解

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        string res;
        for(auto num:nums)
            strs.push_back(to_string(num));
        sort(strs.begin(),strs.end(),compare);
        for(auto str:strs)
            res+=str;
        return res;
    }

    static bool compare(const string &a,const string &b)
    {
        return a+b<b+a;
    }
};

非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法再sort中调用非静态成员函数。静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问，无须创建任何对象实例就可以访问。同时静态成员函数不可以调用类的非静态成员。