मेरा यह प्रश्न हाल ही में एक साक्षात्कार में था और मैं असफल रहा, और अब उत्तर की खोज करता हूं।

  1. मान लीजिए कि मेरे पास एन पूर्णांक, सभी विभेदकों की एक बड़ी सरणी है।

  2. यदि इस सरणी का आदेश दिया गया था, तो मैं इसे x छोटे में घटा सकता हूं सरणियों, आकार y के सभी, शायद पिछले एक को छोड़कर, जो कम हो सकता है। मैं nth सबर्रे निकालने और इसे वापस करने से पहले ही हल कर सकता था।

उदाहरण: ऐरे ४ ४ २ ५ १ ६ ३। यदि य = २ और मुझे २ वां क्रम चाहिए, तो यह ३ ४ होगा।

अब मैंने जो किया वह केवल सरणी को क्रमबद्ध करना और n n सबर्रे को वापस करना है, जो O ({X0}}) लेता है। लेकिन यह मेरे लिए कहा गया था कि इसे O(n + y log y) करने का एक तरीका मौजूद है। मैंने इंटरनेट पर खोज की और कुछ भी नहीं मिला। विचार?

11
Bene Tleilax 27 नवम्बर 2015, 15:30

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)

16
Sergey Kalinichenko 27 नवम्बर 2015, 12:38

आप 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 जैसे विशेष मामलों के लिए जाँच की जाए, लेकिन यह सामान्य विचार है।

5
Baum mit Augen 27 नवम्बर 2015, 12:48