समस्या
Both lists are sorted in ascending order. Find the median of all their numbers together; for an even count it is the average of the two middle values. An O(log(m + n)) partition search is possible, but any correct method within the limits is accepted.
Implement median_of_two(first, second).
Input
first: A sorted list. second: A sorted list.
Output
Return the median.
सीमाएँ
0 ≤ lengths ≤ 100,000; the combined length is at least 1
उदाहरण
इनपुट:
first = [1, 3]
second = [2]
अपेक्षित आउटपुट:
expected = 2.0इनपुट:
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};
अपेक्षित आउटपुट:
double expected = 2.0;इनपुट:
long[] first = new long[] {1, 3};
long[] second = new long[] {2};
अपेक्षित आउटपुट:
double expected = 2.0;व्याख्या
Combined: [1, 2, 3]; the middle value is 2.
इनपुट:
first = [1, 2]
second = [3, 4]
अपेक्षित आउटपुट:
expected = 2.5इनपुट:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};
अपेक्षित आउटपुट:
double expected = 2.5;इनपुट:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};
अपेक्षित आउटपुट:
double expected = 2.5;व्याख्या
Combined: [1, 2, 3, 4]; (2 + 3) / 2 = 2.5.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Combined order ज़रूरी है, लेकिन अगर middle split सीधे मिल जाए तो सब merge करने की ज़रूरत नहीं.
संकेत 2
ऐसा partition खोजें जहाँ left halves में ठीक lower middle elements हों और हर left value हर right value से छोटी या बराबर हो.
संकेत 3
empty arrays और odd/even total length दोनों को ध्यान से handle करें, क्योंकि median एक middle value या दो values से आ सकता है.
अपेक्षित जटिलता
समय O(log(min(m, n))), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।