โจทย์
Join ของ LINQ จับคู่รายการจากสองลำดับด้วยคีย์ที่ใช้ร่วมกัน คล้ายการ join ในฐานข้อมูล ในที่นี้ลูกค้าถูกจับคู่กับคำสั่งซื้อด้วยรหัสลูกค้า
ลูกค้า i มีรหัส customer_ids[i] และชื่อ customer_names[i] คำสั่งซื้อแต่ละรายการคือ [customer_id, amount]
จับคู่ทั้งสอง: สำหรับลูกค้าแต่ละคนที่มีคำสั่งซื้ออย่างน้อยหนึ่งรายการ ให้รวมยอดของคำสั่งซื้อ ลูกค้าที่ไม่มีคำสั่งซื้อไม่ต้องแสดง และคำสั่งซื้อที่รหัสลูกค้าไม่มีอยู่จะถูกข้าม
จงเขียน join_customers_orders(customer_ids, customer_names, orders)
อินพุต
customer_ids, customer_names: ลูกค้า (รหัสไม่ซ้ำกัน)
orders: คู่ [customer_id, amount]
เอาต์พุต
คืนค่า "<name>:<total>" ของลูกค้าแต่ละคนที่มีคำสั่งซื้อ เรียงตามยอดรวมจากมากไปน้อย และตามชื่อ (ลำดับรหัสอักขระ) เมื่อยอดรวมเท่ากัน
เงื่อนไข
1 ≤ จำนวนลูกค้า ≤ 10,000
0 ≤ จำนวนคำสั่งซื้อ ≤ 100,000; 1 ≤ amount ≤ 10^6
ตัวอย่าง
อินพุต:
orders = [
[1, 50],
[2, 30],
[1, 20]
]
customer_ids = [1, 2, 3]
customer_names = ["Ada", "Lin", "Bo"]
ผลลัพธ์ที่คาดหวัง:
expected = ["Ada:70", "Lin:30"]
อินพุต:
std::vector<std::vector<long long>> orders = {
{1, 50},
{2, 30},
{1, 20}
};
std::vector<long long> customer_ids = {1, 2, 3};
std::vector<std::string> customer_names = {"Ada", "Lin", "Bo"};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Ada:70", "Lin:30"};
อินพุต:
long[][] orders = new long[][] {
new long[] {1, 50},
new long[] {2, 30},
new long[] {1, 20}
};
long[] customer_ids = new long[] {1, 2, 3};
string[] customer_names = new string[] {"Ada", "Lin", "Bo"};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Ada:70", "Lin:30"};
คำอธิบาย
Ada มีสองคำสั่งซื้อ (50 + 20 = 70) และ Lin มีหนึ่ง (30) ส่วน Bo ไม่มีจึงไม่แสดง: ["Ada:70", "Lin:30"]
อินพุต:
orders = [
[8, 40],
[7, 40],
[9, 99]
]
customer_ids = [7, 8]
customer_names = ["Zoe", "Max"]
ผลลัพธ์ที่คาดหวัง:
expected = ["Max:40", "Zoe:40"]
อินพุต:
std::vector<std::vector<long long>> orders = {
{8, 40},
{7, 40},
{9, 99}
};
std::vector<long long> customer_ids = {7, 8};
std::vector<std::string> customer_names = {"Zoe", "Max"};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Max:40", "Zoe:40"};
อินพุต:
long[][] orders = new long[][] {
new long[] {8, 40},
new long[] {7, 40},
new long[] {9, 99}
};
long[] customer_ids = new long[] {7, 8};
string[] customer_names = new string[] {"Zoe", "Max"};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Max:40", "Zoe:40"};
คำอธิบาย
ทั้งสองมียอด 40 จึงเรียงตามชื่อ คำสั่งซื้อของรหัส 9 ที่ไม่มีอยู่ถูกข้าม: ["Max:40", "Zoe:40"]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ขั้นแรกรวมยอดคำสั่งซื้อตามรหัสลูกค้า
คำใบ้ 2
จากนั้นไล่ดูลูกค้าและเก็บคนที่มียอดรวม
คำใบ้ 3
เรียงตามยอดรวมจากมากไปน้อย แล้วตามชื่อตามลำดับรหัสอักขระ
ความซับซ้อนที่คาดหวัง
เวลา O(n log n), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน