सूची में kवाँ सबसे छोटा तत्व
आपको
n पूर्णांक दिए गए हैं, साथ ही एक संख्या k भी दी गई है। आपका कार्य सूची में kवाँ सबसे छोटा तत्व खोजना है। यह सुनिश्चित किया गया है कि सूची के सभी तत्व आपस में भिन्न (distinct) हैं।इनपुट
इनपुट की पहली पंक्ति में दो संख्याएँ
n और k होती हैं (1 ≤ k ≤ n ≤ )।अगली पंक्ति में
n स्पेस से अलग किए हुए पूर्णांक दिए होते हैं: ()।आउटपुट
कार्यक्रम को सूची में
kवाँ सबसे छोटा तत्व प्रिंट करना चाहिए।उदाहरण
इनपुट | आउटपुट |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -3 |
स्पष्टीकरण
- सूची को छांटने पर परिणाम [-2, 3, 4, 6, 8, 10] होता है, अतः 3रा सबसे छोटा तत्व 4 है।
- सूची को छांटने पर परिणाम [-4, -3, 0, 5, 7, 8, 10] होता है, अतः 2रा सबसे छोटा तत्व -3 है।
Hint 1
रैंडम पार्टिशनिंग (random partitioning) का उपयोग करें, जो QuickSort के समान है।
तत्वों को सीधे छांटने के लिए यहाँ समय की पाबंदी काफी कड़ी होगी।
Hint 2
आप पिवट (pivot) को रैंडम तरीके से चुनकर, QuickSort जैसी प्रक्रिया अपनाते हुए पूरी सूची को दो भागों में बाँट सकते हैं। इसके बाद आपको केवल उस हिस्से को संभालना है, जहाँ आपका
kवाँ तत्व मौजूद हो सकता है, और बाकी हिस्से को अनदेखा कर सकते हैं।यह प्रक्रिया तब तक दोहराएँ जब तक वह हिस्सा, जो आपके इच्छित आइटम से पहले नज़रअंदाज़ हो चुका है, ठीक
k तत्वों के बराबर न हो जाए।रैंडम पार्टिशनिंग का अपेक्षित समय है। क्या आपको पता है क्यों?
Hint 3
हर बार जब हम सूची में रैंडम तरीके से पार्टिशन करते हैं, तो औसत रूप से सूची का आकार आधा हो जाता है। मान लीजिए कि किसी चरण में सूची का आकार
n है, तो पार्टिशन के बाद हम क़रीब n/2 को अलग कर देते हैं; दूसरी बार हम बचे हुए n/2 में से भी n/4 को हटाते हैं, और इसी तरह आगे बढ़ते हैं। अंततः यह कुल योग बनता है: ।लेकिन, अगर रैंडम पिवट बार-बार ऐसा चुना जाए कि सूची अपेक्षित रूप से आधी न बँट पाए, तब यह एल्गोरिदम तक भी जा सकता है।
Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB