पूर्णांक की अनारक्षित सूची में न्यूनतम न्यूनतम मानों के लिए इष्टतम खोज

Question

मुझे अभी एक प्रश्न के साथ साक्षात्कार दिया गया था, और मुझे उत्सुकता है कि उत्तर क्या होना चाहिए। समस्या थी, अनिवार्य रूप से:

कहें कि आपके पास एन पूर्णांक की एक अपरिवर्तित सूची है। आप इस सूची में के न्यूनतम मान कैसे प्राप्त करते हैं? यही है, यदि आपके पास [10, 11, 24, 12, 13] की सूची है और आप 2 न्यूनतम मानों की तलाश में हैं, तो आपको [10, 11] मिल जाएगा।

मुझे ओ (एन * लॉग (के)) समाधान मिला है, और यह मेरा सबसे अच्छा है, लेकिन मैं उत्सुक हूं कि अन्य लोग क्या आते हैं। मैं अपने समाधान को पोस्ट करके प्रदूषित लोगों के दिमाग से बचना होगा और इसे थोड़ी देर में संपादित कर दूंगा।

संपादित करें # 1: उदाहरण के लिए, की तरह एक समारोह: सूची getMinVals (सूची & एल, पूर्णांक ट)

संपादित करें # 2: ऐसा लगता है कि यह एक चयन एल्गोरिथ्म है जैसे, इसलिए मैं अपने समाधान में टॉस जाएगा भी; सूची में पुनरावृत्ति, और न्यूनतम मानों को बचाने के लिए प्राथमिकता कतार का उपयोग करना। प्राथमिकता कतार पर कल्पना यह थी कि अधिकतम मूल्य प्राथमिकता कतार के शीर्ष पर समाप्त हो जाएंगे, इसलिए शीर्ष पर एक तत्व की तुलना करने पर, शीर्ष पॉप हो जाएगा और छोटे तत्व को धक्का दिया जाएगा। इसने माना कि प्राथमिकता कतार में ओ (लॉग एन) पुश और ओ (1) पॉप था।

Answer 1

यह quickSelect एल्गोरिदम है। यह मूल रूप से एक त्वरित प्रकार है जहां आप केवल सरणी के एक हिस्से के लिए रिकर्स करते हैं। यहां पाइथन में एक सरल कार्यान्वयन है, जो दक्षता के बजाय ब्रेवटी और पठनीयता के लिए लिखा गया है।

def quickSelect(data, nLeast) : 
    pivot = data[-1] 
    less = [x for x in data if x <= pivot] 
    greater = [x for x in data if x > pivot] 
    less.append(pivot) 

    if len(less) < nLeast : 
     return less + quickSelect(greater, nLeast - len(less)) 
    elif len(less) == nLeast : 
     return less 
    else : 
     return quickSelect(less, nLeast) 

यह हे (एन) औसतन में चलेंगे, क्योंकि हर यात्रा पर, आप एक गुणक निरंतर द्वारा data के आकार को कम करने के लिए उम्मीद कर रहे हैं। नतीजा हल नहीं किया जाएगा। सबसे बुरा मामला ओ (एन^2) है, लेकिन यह अनिवार्य रूप से उसी तरह से निपटाया जाता है जैसे कि औसत-जैसे-3 जैसी चीजों का उपयोग करना।

Answer 2

यह आमतौर पर selection algorithms या "रैखिक चयन" के तहत एल्गोरिदम पुस्तकें में होता है। यहां विशिष्ट section on min/max k values in a list है। यह ओ (नलॉग (के)) है।