समस्या
LINQ का Join दो क्रमों के आइटम को एक साझा की से मिलाता है, डेटाबेस join की तरह। यहाँ ग्राहकों को ग्राहक id से उनके ऑर्डर से मिलाया जाता है।
ग्राहक i की id customer_ids[i] और नाम customer_names[i] है। हर ऑर्डर [customer_id, amount] है।
दोनों को जोड़ें: कम से कम एक ऑर्डर वाले हर ग्राहक के लिए उसके ऑर्डर की रकम जोड़ें। बिना ऑर्डर वाले ग्राहक छोड़ दिए जाते हैं, और अनजान ग्राहक id वाले ऑर्डर अनदेखे किए जाते हैं।
join_customers_orders(customer_ids, customer_names, orders) लिखें।
इनपुट
customer_ids, customer_names: ग्राहक (id अलग-अलग हैं)।
orders: [customer_id, amount] जोड़ियाँ।
आउटपुट
ऑर्डर वाले हर ग्राहक के लिए "<name>:<total>" लौटाएँ, कुल के घटते क्रम में, और कुल बराबर हो तो नाम (ordinal क्रम) से।
सीमाएँ
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 है, इसलिए नाम से क्रम; अनजान id 9 का ऑर्डर अनदेखा: ["Max:40", "Zoe:40"]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
पहले हर ग्राहक id के ऑर्डर की रकम जोड़ें।
संकेत 2
फिर ग्राहकों पर चलें और जिनका कुल है उन्हें रखें।
संकेत 3
कुल के घटते क्रम में, फिर नाम के ordinal क्रम में सॉर्ट करें।
अपेक्षित जटिलता
समय O(n log n), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।