समस्या
मानों को आरोही क्रम में छांटें। यदि मानों की संख्या विषम है, तो मध्य वाला मान लें। यदि मानों की संख्या सम है, तो दो मध्य मानों का अंकगणितीय औसत लें। यह चुनौती केवल गैर-खाली सूचियों को स्वीकार करती है।
median_number(numbers) को लागू करें।
इनपुट
numbers: मानों की गैर-खाली सूची।
आउटपुट
माध्यिका को एक संख्या के रूप में लौटाएँ; यह .5 पर समाप्त हो सकती है।
सीमाएँ
1 ≤ सूची की लंबाई ≤ 100,000। प्रत्येक मान −1,000,000,000 और 1,000,000,000 के बीच का पूर्णांक है।
उदाहरण
इनपुट:
numbers = [2, 8, 4, 10]
अपेक्षित आउटपुट:
expected = 6.0इनपुट:
std::vector<long long> numbers = {2, 8, 4, 10};
अपेक्षित आउटपुट:
double expected = 6.0;इनपुट:
long[] numbers = new long[] {2, 8, 4, 10};
अपेक्षित आउटपुट:
double expected = 6.0;व्याख्या
छांटा हुआ क्रम है 2, 4, 8, 10। मध्य के दो मानों का औसत (4 + 8) / 2 = 6 है।
इनपुट:
numbers = [9, 1, 4]
अपेक्षित आउटपुट:
expected = 4.0इनपुट:
std::vector<long long> numbers = {9, 1, 4};
अपेक्षित आउटपुट:
double expected = 4.0;इनपुट:
long[] numbers = new long[] {9, 1, 4};
अपेक्षित आउटपुट:
double expected = 4.0;व्याख्या
छांटा हुआ क्रम है 1, 4, 9, जिसका मध्य मान 4 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Median sorted order पर निर्भर करता है, इसलिए sorted list में positions मायने रखती हैं।
संकेत 2
Sort करने के बाद odd length के लिए बीच वाला element लें, और even length के लिए दो middle elements को combine करें।
संकेत 3
Two middle values का average लेते समय halves preserve करना याद रखें, क्योंकि answer .5 पर खत्म हो सकता है।
अपेक्षित जटिलता
समय O(n log n), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।