Sắp xếp mảng các số nguyên lớn được biểu diễn bằng string

minhcanhtu · September 2, 2018, 3:07pm

Mình co đang giải challenge sau của hackerrank: https://www.hackerrank.com/challenges/big-sorting/problem

Mình chỉ dùng bubble sort để sắp xếp vector các chuỗi cho trước:

// Complete the bigSorting function below.
vector<string> bigSorting(vector<string> unsorted) {
    int n = unsorted.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if ((unsorted[i] > unsorted[j] && unsorted[i].size() == unsorted[j].size()) || (unsorted[i].size() > unsorted[j].size())) swap(unsorted[i], unsorted[j]);
        }
    }
    return unsorted;
}

Với bubble sort thì chỉ vượt qua 7/9 testcases (2 testcase 6 và 7 bị Terminated due to timeout!). Mình có thử cài đặt Quicksort để sort thì gặp nhiều lỗi quá, ko biết mọi người có cách làm nào khá hơn không?

tntxtnt · September 2, 2018, 4:55pm

xài std::sort có sẵn trong <algorithm> ấy

bình thường sort viết là

std::sort(begin(a), end(a));

bây giờ muốn so sánh khác so sánh x < y thì thêm vào hàm so sánh:

std::sort(begin(a), end(a), myCustomComparator);

trong đó myCustomComparator là 1 hàm/functor/lambda có input là 2 giá trị cần so sánh, output là true nếu giá trị đầu đứng trước giá trị sau sau khi được sắp xếp

nếu xài hàm:

bool myCustomComparator(const std::string& lhs, const std::string& rhs)
{
    //return lhs < rhs; //so sánh thế nào viết tại đây
}
//...
std::sort(begin(a), end(a), myCustomComparator);

nếu xài functor thì phải có operator():

struct MyCustomComparator {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        //return lhs < rhs; //so sánh thế nào viết tại đây
    }
};
//...
std::sort(begin(a), end(a), MyCustomComparator{}); //MyCustomComparator{} là 1 biến tạm thời được tạo ra để sort, sort xong thì tự động xóa

nếu xài lambda thì viết thẳng luôn:

std::sort(begin(a), end(a),
    [](const std::string& lhs, const std::string& rhs) {
        //return lhs < rhs; //so sánh thế nào viết tại đây
    });

minhcanhtu · September 3, 2018, 12:16am

Em chưa hiểu chỗ này lắm, anh có thể nói rõ hơn được ko?

Em chọn cách 1 và viết lại code như sau thì pass: https://ideone.com/a8X8Dx

tntxtnt · September 3, 2018, 1:13am

nghĩa là f(x, y) trả về true nếu x đứng trước y đó mà. Từ định nghĩa này ta có

f(x, x) phải là false (x ko đứng trước chính nó)
nếu f(x, y) là true thì f(y, x) phải là false
nếu f(x, y) là true và f(y, z) là true thì f(x, z) phải là true
ngoài ra còn có tính bắc cầu cho trường hợp bằng nhau: nếu x == y và y == z thì x == z. (x == y nếu f(x, y) và f(y, x) đều là false)

ví dụ hàm so sánh bé hơn hoặc bằng x <= y hay lớn hơn hoặc bằng x >= y ko thỏa tiêu chí này. Hàm so sánh lớn hơn x > y lại thỏa tiêu chí này, nên nói “x đứng trước y” cho nó tổng quát chứ nói “x bé hơn y” thì ko tổng quát cho mọi trường hợp.

tiếng Anh goi là strict weak ordering, tài liệu của thư viện STL đây: http://www.oopweb.com/CPP/Documents/STLGuide/Volume/StrictWeakOrdering.html