मेरा यह प्रश्न हाल ही में एक साक्षात्कार में था और मैं असफल रहा, और अब उत्तर की खोज करता हूं।
मान लीजिए कि मेरे पास एन पूर्णांक, सभी विभेदकों की एक बड़ी सरणी है।
यदि इस सरणी का आदेश दिया गया था, तो मैं इसे x छोटे में घटा सकता हूं सरणियों, आकार y के सभी, शायद पिछले एक को छोड़कर, जो कम हो सकता है। मैं nth सबर्रे निकालने और इसे वापस करने से पहले ही हल कर सकता था।
उदाहरण: ऐरे ४ ४ २ ५ १ ६ ३। यदि य = २ और मुझे २ वां क्रम चाहिए, तो यह ३ ४ होगा।
अब मैंने जो किया वह केवल सरणी को क्रमबद्ध करना और n n सबर्रे को वापस करना है, जो O ({X0}}) लेता है। लेकिन यह मेरे लिए कहा गया था कि इसे O(n + y log y) करने का एक तरीका मौजूद है। मैंने इंटरनेट पर खोज की और कुछ भी नहीं मिला। विचार?
2 जवाब
आप जिस एल्गोरिथ्म की तलाश कर रहे हैं, वह चयन एल्गोरिदम है, जो आपको k-th ऑर्डर आँकड़े । एल्गोरिथ्म काफी जटिल है, लेकिन मानक C ++ लाइब्रेरी आसानी से एक कार्यान्वयन प्रदान करती है।
के-वें क्रमबद्ध अंतराल को खोजने के लिए एल्गोरिदम जो साक्षात्कारकर्ताओं के दिमाग में था, इस तरह से चला गया:
b=(k-1)*yखोजें - O (N) में वें क्रम के आँकड़ेe=k*yखोजें - O (N) में वें क्रम के आँकड़ेbऔरeके बीचyनंबर होंगे। उन्हेंyआकार के एक अलग सरणी में संग्रहीत करें। यह ऑपरेशन O (N) लेता है- O (y * log 2 y) लागत के लिए आकार की
yक्रमबद्ध करें।
कुल लागत O (N + N + N + y * लॉग <उप> 2 y) है, अर्थात O (N + y * लॉग <उप> 2 y)
आप std::nth_element और std::sort
std::vector<int> vec = muchData();
// Fix those bound iterators as needed
auto lower = vec.begin() + k*y;
auto upper = lower + y;
// put right element at lower and partition vector by it
std::nth_element(vec.begin(), lower, vec.end());
// Same for upper, but don't mess up lower
std::nth_element(lower + 1, upper - 1, vec.end());
// Now sort the subarray
std::sort(lower, upper);
[lower, upper) अब औसतन वांछित जटिलता के साथ लंबाई y का k-th सॉर्टेड सबरेरी है।
वास्तविक दुनिया के उपयोग से पहले y = 1 जैसे विशेष मामलों के लिए जाँच की जाए, लेकिन यह सामान्य विचार है।
संबंधित सवाल
नए सवाल
c++
C ++ एक सामान्य-प्रयोजन प्रोग्रामिंग भाषा है। यह मूल रूप से C के विस्तार के रूप में डिज़ाइन किया गया था और इसमें एक समान सिंटैक्स है, लेकिन यह अब पूरी तरह से अलग भाषा है। C ++ कंपाइलर के साथ संकलित कोड के बारे में प्रश्नों के लिए इस टैग का उपयोग करें। विशिष्ट मानक संशोधन [C ++ 11], [C ++ 14], [C ++ 17], [C ++ 20] या [C ++ 23], आदि से संबंधित प्रश्नों के लिए संस्करण-विशिष्ट टैग का उपयोग करें। ।