拼数

链接

此题要求我们找出最大的数字拼起来

但是数字可能过大无法进行比较,我们可以采用字符串比较方法

比如123321和321123比较,肯定后者更大,因为3的ASCII值比1的大(位数一样的情况)

不过,我们不需要考虑位数123和321拼起来的数的位数肯定一样

我们再结合sort函数,写一套自己的排序规则

最后把排好序的数组的元素全部加起来即可

代码实现

#include<bits/stdc++.h>
using namespace std;
bool compare(string a,string b){
    return a+b>b+a;
}
int main(){
    int n;
    cin>>n;
    vector<string>ans;
    for(int i=0;i<n;i++){
        string num;cin>>num;
        ans.push_back(num);
    }
    string result;
    sort(ans.begin(),ans.end(),compare);
    for(string num:ans){
        result+=num;
    }
    cout<<result;
}

时间复杂度:O(n log n * m)，其中 m 是字符串平均长度

空间复杂度:O(n * m)