Đề bài
Trong C#, một IComparer<T> là một interface: bất kỳ lớp nào triển khai phương thức Compare của nó đều có thể cho biết phần tử nào đứng trước trong một lần sắp xếp. Việc chọn một comparer khác sẽ thay đổi thứ tự mà không cần thay đổi cách sắp xếp.
Sắp xếp mọi người theo key:
name: theo tên (thứ tự ký tự ordinal, vì vậy chữ in hoa đứng trước chữ in thường), và theo tuổi khi tên giống nhau.age: theo tuổi, người trẻ hơn đứng trước, và theo tên khi tuổi giống nhau.
Hãy triển khai sort_by_key(names, ages, key).
Đầu vào
names, ages: Những người (cùng độ dài).
key: "name" hoặc "age".
Đầu ra
Trả về các tên theo thứ tự đã sắp xếp.
Ràng buộc
0 ≤ số người ≤ 100,000
0 ≤ tuổi ≤ 150
Ví dụ
Đầu vào:
key = "age"
ages = [30, 36, 30]
names = ["Lin", "Ada", "Bo"]
Kết quả mong đợi:
expected = ["Bo", "Lin", "Ada"]Đầu vào:
std::string key = "age";
std::vector<long long> ages = {30, 36, 30};
std::vector<std::string> names = {"Lin", "Ada", "Bo"};
Kết quả mong đợi:
std::vector<std::string> expected = {"Bo", "Lin", "Ada"};Đầu vào:
string key = "age";
long[] ages = new long[] {30, 36, 30};
string[] names = new string[] {"Lin", "Ada", "Bo"};
Kết quả mong đợi:
string[] expected = new string[] {"Bo", "Lin", "Ada"};Giải thích
Bo và Lin đều 30 tuổi, nên chúng được sắp xếp theo tên trước Ada (36): ["Bo", "Lin", "Ada"].
Đầu vào:
key = "name"
ages = [30, 36, 30]
names = ["Lin", "Ada", "Bo"]
Kết quả mong đợi:
expected = ["Ada", "Bo", "Lin"]Đầu vào:
std::string key = "name";
std::vector<long long> ages = {30, 36, 30};
std::vector<std::string> names = {"Lin", "Ada", "Bo"};
Kết quả mong đợi:
std::vector<std::string> expected = {"Ada", "Bo", "Lin"};Đầu vào:
string key = "name";
long[] ages = new long[] {30, 36, 30};
string[] names = new string[] {"Lin", "Ada", "Bo"};
Kết quả mong đợi:
string[] expected = new string[] {"Ada", "Bo", "Lin"};Giải thích
Thứ tự theo bảng chữ cái: ["Ada", "Bo", "Lin"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Sắp xếp các cặp (name, age) thay vì hai danh sách riêng.
Gợi ý 2
Khóa được chọn quyết định thứ tự chính; trường còn lại phân định hòa.
Gợi ý 3
Dùng so sánh chuỗi ordinal để chữ hoa đứng trước chữ thường.
Độ phức tạp mong đợi
thời gian O(n log n), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.