剑指45：把数组排成最小的数

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    定义排序方法：
        比较两个字符串 S1 和 S2 的大小时，应该比较 S1+S2 和 S2+S1 的大小，
        若 S1+S2 < S2+S1，则 S1 排在前面；否则，S2 排在前面。
*/
class Solution {
public:
    string PrintMinNumber(vector<int>& nums) {
        vector<string> numStr;
        for (auto num : nums) {
            numStr.push_back(to_string(num));
        }
        sort(numStr.begin(), numStr.end(), [](const string & a, const string & b) {
            return a + b < b + a;
        });

        string res;
        for (auto t : numStr) {
            res += t;
        }
        return res;
    }
};

/*
    sort 中比较函数 compare 要求声明为静态成员函数或全局函数，作为普通成员函数会报错。
    非静态成员函数依赖于具体对象，而 std::sort 这类函数是全局的，不能调用非静态成员函数。
*/
class Solution {
public:
    string PrintMinNumber(vector<int>& nums) {
        string res = "";
        sort(nums.begin(), nums.end(), cmp);
        for (auto& num : nums) {
            res += to_string(num);
        }
        return res;
    }

    static bool cmp(int a, int b) {
        string A = "", B = "";
        A = to_string(a) + to_string(b);
        B = to_string(b) + to_string(a);
        return A < B;
    }
};

C++ 代码 - leetcode

/*
    定义排序方法：
        比较两个字符串 S1 和 S2 的大小时，应该比较 S1+S2 和 S2+S1 的大小，
        若 S1+S2 < S2+S1，则 S1 排在前面；否则，S2 排在前面。
*/
class Solution {
public:
    string crackPassword(vector<int>& nums) {
        int n = nums.size();
        vector<string> res(n);
        for (int i = 0; i < n; i ++) {
            res[i] = to_string(nums[i]);
        }
        sort(res.begin(), res.end(), [](const string& s1, const string& s2) {
            // 不用转成 int 类型，字符串和正整数的比较算法是一样的
            // 拼接字符串比较长，会导致 int 类型溢出
            return (s1 + s2) < (s2 + s1);
        });

        return accumulate(res.begin(), res.end(), string(""));
    }
};