Đề bài
Join của LINQ ghép các phần tử từ hai dãy theo một khóa chung, giống phép join trong cơ sở dữ liệu. Ở đây khách hàng được ghép với đơn hàng theo mã khách hàng.
Khách hàng i có mã customer_ids[i] và tên customer_names[i]. Mỗi đơn hàng là [customer_id, amount].
Hãy ghép hai dãy: với mỗi khách có ít nhất một đơn, cộng số tiền các đơn của họ. Khách không có đơn bị bỏ qua, và đơn có mã khách hàng không tồn tại cũng bị bỏ qua.
Hãy viết join_customers_orders(customer_ids, customer_names, orders).
Đầu vào
customer_ids, customer_names: Các khách hàng (mã không trùng nhau).
orders: Các cặp [customer_id, amount].
Đầu ra
Trả về "<name>:<total>" cho mỗi khách có đơn, sắp theo tổng từ cao xuống thấp, và theo tên (thứ tự ordinal) khi tổng bằng nhau.
Ràng buộc
1 ≤ số khách hàng ≤ 10,000
0 ≤ số đơn hàng ≤ 100,000; 1 ≤ amount ≤ 10^6
Ví dụ
Đầu vào:
orders = [
[1, 50],
[2, 30],
[1, 20]
]
customer_ids = [1, 2, 3]
customer_names = ["Ada", "Lin", "Bo"]
Kết quả mong đợi:
expected = ["Ada:70", "Lin:30"]Đầu vào:
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"};
Kết quả mong đợi:
std::vector<std::string> expected = {"Ada:70", "Lin:30"};Đầu vào:
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"};
Kết quả mong đợi:
string[] expected = new string[] {"Ada:70", "Lin:30"};Giải thích
Ada có hai đơn (50 + 20 = 70) và Lin một đơn (30); Bo không có đơn nên bị bỏ qua: ["Ada:70", "Lin:30"].
Đầu vào:
orders = [
[8, 40],
[7, 40],
[9, 99]
]
customer_ids = [7, 8]
customer_names = ["Zoe", "Max"]
Kết quả mong đợi:
expected = ["Max:40", "Zoe:40"]Đầu vào:
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"};
Kết quả mong đợi:
std::vector<std::string> expected = {"Max:40", "Zoe:40"};Đầu vào:
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"};
Kết quả mong đợi:
string[] expected = new string[] {"Max:40", "Zoe:40"};Giải thích
Cả hai đều có tổng 40 nên xếp theo tên; đơn của mã 9 không tồn tại bị bỏ qua: ["Max:40", "Zoe:40"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Trước tiên cộng số tiền đơn hàng theo từng mã khách hàng.
Gợi ý 2
Sau đó duyệt danh sách khách và giữ những người có tổng.
Gợi ý 3
Sắp theo tổng giảm dần, rồi theo tên theo thứ tự ordinal.
Độ 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.