Tạo số lớn nhất theo thứ tự từ điển từ danh sách số trong C++

Giả sử chúng ta có một danh sách số gọi là nums, ta phải sắp xếp lại thứ tự của nó để tạo thành số lớn nhất có thể và trả về dưới dạng chuỗi.

Ví dụ: nếu đầu vào là nums = [20, 8, 85, 316], đầu ra sẽ là "88531620".

Phương pháp giải

Để giải quyết, ta thực hiện các bước:

• Tạo mảng tạm temp
• Với mỗi phần tử i trong nums: chuyển i thành chuỗi và thêm vào temp
• Sắp xếp mảng temp dựa trên thứ tự từ điển (so sánh hai chuỗi a, b xem a+b lớn hơn b+a hay không)
• Ghép nối tất cả chuỗi s trong temp vào kết quả res
• Trả về res

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;

static bool cmp(string a, string b) {
    return (a + b) >= (b + a);
}

string solve(vector<int>& nums) {
    vector<string> temp;
    for (int i : nums)
        temp.push_back(to_string(i));
    
    sort(temp.begin(), temp.end(), cmp);
    
    string res;
    for (string s : temp)
        res += s;
    
    return res;
}

int main() {
    vector<int> v = {20, 8, 85, 316};
    cout << solve(v);
    return 0;
}

Đầu vào

{20, 8, 85, 316}

Đầu ra

88531620