โจทย์
ใน C#, IComparer<T> คือ interface: คลาสใดก็ตามที่ implement เมธอด Compare ของมันได้ ก็สามารถบอกให้การ sort ทราบว่า item ใดมาก่อน การเลือก comparer คนละตัวจะเปลี่ยนลำดับได้โดยไม่ต้องเปลี่ยนการ sort
จงเรียงคนตาม key:
name: เรียงตามชื่อ (ลำดับอักขระแบบ ordinal ดังนั้นตัวพิมพ์ใหญ่จะมาก่อนตัวพิมพ์เล็ก) และเรียงตามอายุเมื่อชื่อเหมือนกัน.age: เรียงตามอายุ โดยอายุน้อยมาก่อน และเรียงตามชื่อเมื่ออายุเท่ากัน.
จงเขียน sort_by_key(names, ages, key).
อินพุต
names, ages: คนเหล่านี้ (ยาวเท่ากัน).
key: "name" หรือ "age".
เอาต์พุต
คืนชื่อที่เรียงแล้ว.
เงื่อนไข
0 ≤ จำนวนคน ≤ 100,000
0 ≤ อายุ ≤ 150
ตัวอย่าง
อินพุต:
key = "age"
ages = [30, 36, 30]
names = ["Lin", "Ada", "Bo"]
ผลลัพธ์ที่คาดหวัง:
expected = ["Bo", "Lin", "Ada"]
อินพุต:
std::string key = "age";
std::vector<long long> ages = {30, 36, 30};
std::vector<std::string> names = {"Lin", "Ada", "Bo"};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Bo", "Lin", "Ada"};
อินพุต:
string key = "age";
long[] ages = new long[] {30, 36, 30};
string[] names = new string[] {"Lin", "Ada", "Bo"};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Bo", "Lin", "Ada"};
คำอธิบาย
Bo และ Lin อายุ 30 เท่ากัน ดังนั้นจึงเรียงตามชื่อก่อน Ada (36): ["Bo", "Lin", "Ada"].
อินพุต:
key = "name"
ages = [30, 36, 30]
names = ["Lin", "Ada", "Bo"]
ผลลัพธ์ที่คาดหวัง:
expected = ["Ada", "Bo", "Lin"]
อินพุต:
std::string key = "name";
std::vector<long long> ages = {30, 36, 30};
std::vector<std::string> names = {"Lin", "Ada", "Bo"};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Ada", "Bo", "Lin"};
อินพุต:
string key = "name";
long[] ages = new long[] {30, 36, 30};
string[] names = new string[] {"Lin", "Ada", "Bo"};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Ada", "Bo", "Lin"};
คำอธิบาย
ลำดับตัวอักษร: ["Ada", "Bo", "Lin"].
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
เรียงคู่ (name, age) แทนการแยกเป็นสองลิสต์
คำใบ้ 2
คีย์ที่เลือกกำหนดลำดับหลัก อีกฟิลด์ใช้ตัดสินเมื่อเท่ากัน
คำใบ้ 3
เทียบสตริงตามรหัสอักขระ ตัวพิมพ์ใหญ่จึงมาก่อนตัวพิมพ์เล็ก
ความซับซ้อนที่คาดหวัง
เวลา O(n log n), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน