一、题目描述

题目大意：给定一个nums数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出
注意审题：由一些非负整数组成，因此不必考虑负数的情况

二、算法一（排序）

解题思路

  1. 要使得拼接出的数尽可能的大，一种直观的想法就是令拼接出的数高位尽可能的大，这样整体就更大。对于两个数a、b，要求得最大值，直接比较两者拼接后的大小即可，因此我们可以定义一种比较大小的规则，即若 ab < ba ，则数b小于数a，应该排在数a之前，其中 ab = a * 10^count(b) + b (count(b)为b的位数)
  2. 当元素个数大于2时，我们只要证明了这种比较规则是满足传递性，就可以确定两个元素在排序后的相对位置关系，当确定了所有数的相对位置关系之后，整个数组拼接成的序列就是最终的结果
  3. 当一个数a排在数b使得结果更优时，我们记作 a#b ，要证明比较规则具有传递性，即证明 a#b 且 b#c 时，满足 a#c，证明如下：
    由 a#b 且 b#c 可知：
  • a * 10^count(b) + b >= b * 10^count(a) + a
  • b * 10^count(c) + c >= c * 10^count(b) + b
    整理得：
  • a * (10^count(b) - 1) >= b * (10^count(a) - 1)
  • b * (10^count(c) - 1) >= c * (10^count(b) - 1)

由于均为非负整数，故将两式相乘得：
a * (10^count(c) - 1) * b * (10^count(b) - 1) >= c * (10^count(a) - 1) * b * (10^count(b) - 1)
为了证明 a#c，我们对b进行分类讨论：
(1) b = 0 时：

  • 10^count(b) = 1，带入得等式两边都为0，此时满足a#c

(2) b > 0 时：

  • b * (10^count(b) - 1) > 0，故等式两边同时除以b * (10^count(b) - 1)
  • 得 a * 10^count(c) - a >= c * 10^count(a) - c，移项得 a * 10^count(c) + c >= c * 10^count(a) + a，满足 a#c
    故得证排序规则具有传递性

代码实现（C++11）

class Solution {
public:
    string solve(vector<int>& nums) {
        // 为防止拼接后溢出
        using LL = long long;
        // 求非负整数x的数位
        auto count = [](int x) -> int {
            if(x == 0) return 1;
            int cnt = 0;
            while(x) {
                ++cnt;
                x /= 10;
            }
            return cnt;
        };

        // 求10的k次幂
        auto qmi = [](int k) -> int {
            int ans = 1, a = 10;
            while(k) {
                if(k & 1) ans *= a;
                a *= a;
                k >>= 1;
            }
            return ans;
        };

        // 自定义排序
        sort(nums.begin(), nums.end(), [=](const int &a, const int &b){
            return (LL)b * qmi(count(a)) + a < (LL)a * qmi(count(b)) + b;
        });

        // 拼接整个字符串
        string ans;
        for(auto &num : nums) {
            ans += to_string(num);
        }

        // 去除前导零
        reverse(ans.begin(), ans.end());
        while(ans.size() > 1 && ans.back() == '0') {
            ans.pop_back();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

时间复杂度：，n为元素个数，时间复杂度取决于排序，使用快速排序，进行了次比较，由于数据每个数都是小于的非负整数，故每次比较的时间可以看做很小的常数，故总的时间复杂度为
空间复杂度：，排序递归深度为

三、算法二（优先级队列）

类似地，利用以上的结论，我们自定义比较规则，不过这里用优先级队列（堆）来实现，先将所有元素入堆，根据自定义的比较规则，每次先出堆的元素优先级更高，即出堆元素与堆中任意数两两组合形成的最大数，出堆元素总在前半部分，故只要依次将元素出堆即可得到最终的结果序列

图片说明

代码实现（C++11）

struct cmp {
    // 为防止拼接后溢出
    using LL = long long;

    // 求非负整数x的数位
    int count(int x) {
                if(x == 0) return 1;
                int cnt = 0;
                while(x) {
                    ++cnt;
                    x /= 10;
                }
                return cnt;
      }

    // 求10的k次幂
    int qmi(int k) {
        int ans = 1, a = 10;
        while(k) {
            if(k & 1) ans *= a;
            a *= a;
            k >>= 1;
        }
        return ans;
    }

    // 重载()运算符
    bool operator()(const int& a, const int& b) noexcept {
        return (LL)b * qmi(count(a)) + a > (LL)a * qmi(count(b)) + b;
    }
};

class Solution {
public:
    string solve(vector<int>& nums) {
        priority_queue<int, vector<int>, cmp> hp(nums.begin(), nums.end());

        // 拼接整个字符串
        string ans;
        while(hp.size()) {
            ans += to_string(hp.top());
            hp.pop();
        }

        // 去除前导零
        reverse(ans.begin(), ans.end());
        while(ans.size() > 1 && ans.back() == '0') {
            ans.pop_back();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

时间复杂度：，n为元素个数，堆的每次插入操作时间复杂度为，共总时间复杂度为
空间复杂度：，堆使用的空间是的