मैं अपने साक्षात्कार के लिए यह मिल गया:साक्षात्कार प्रश्न: रिवर्स जोड़े
नंबर "का आदेश दिया रिवर्स" कहा जाता है, तो एन [i]> एन [जे] मैं < जे के लिए। उदाहरण के लिए, एक सूची में: 3 4 1 6 7 3, रिवर्स ऑर्डर किए गए आइटम (3,1) (4,1) (4,3) (6,3) (7,3) हैं।
ओ (nlogn) समय में उल्टा आदेश वस्तुओं के जोड़े की संख्या कैसे प्राप्त करें।
मर्ज सॉर्ट के संशोधित संस्करण का उपयोग करके ओ (एन लॉग एन) समय में ऐसा करना संभव है। विभाजन को सामान्य के रूप में करें, लेकिन आप विलय के रूप में उलटा गिन सकते हैं। प्रत्येक बार जब आप बाएं सूची से किसी आइटम पर दाएं सूची से कोई आइटम चुनते हैं तो बाएं सूची में शेष वस्तुओं की संख्या से इनवर्जन की गिनती बढ़ जाती है। तो प्रत्येक स्तर पर विचलन की संख्या विलय के दौरान पाए गए विचलनों की संख्या और प्रत्येक रिकर्सिव कॉल द्वारा प्राप्त उलटाई की संख्या है।
आईटीए के पहले अध्याय (मुझे लगता है) से निष्कर्ष ... :) – st0le
आईटीए का पहला अध्याय क्या है? आईटीए क्या है? – dsg
यह एल्गोरिदम, 2E के परिचय के पृष्ठ 40 पर 2.4 डी व्यायाम है। आपको मर्ज सॉर्ट को संशोधित करके ओ (nlogn) सबसे खराब-केस समय में इनवर्जनों की संख्या निर्धारित करने के लिए कहा जाता है। –
नोट, कृपया इस उत्तर के नीचे पढ़ें कि यह समस्या वास्तव में क्यों संभव है। मैंने सवाल गलत पढ़ा।
सामान्य मामले में यह संभव नहीं है। सूची पर विचार करें:
एन, एन -1, एन-2 ... 4, 3, 2, 1
जोड़ेहो जाएगा:
(एन, n-1), (एन , एन -2) ... (एन, 2), (एन, 1), (एन -1, एन -2), (एन -1, एन -3) ... ... (3, 2) (3, 1), (2, 1)
इसलिए O (n^2) जोड़े होते हैं और इसलिए सूची हे में निर्माण (एन एन लॉग इन करें)
हालांकि नहीं किया जा सकता है, तो आप क्या कर सकते हैं यह सूची के एक पास के साथ:
अपने उदाहरण के लिए:
सूची: 3 4 1 6 7 3
दूसरे मद से शुरू
ढेर (3) आइटम (7)
आउटपुट (7, 3)
012,351,ढेर (3, 7) आइटम (6)
खोज और पाते हैं 7, उत्पादन (6, 3)
ढेर (3, 6, 7) आइटम (1)
खोज और कुछ भी नहीं
ढेर लगता है (1, 3, 6, 7) आइटम (4)
खोज और पाते हैं 3 और 1 निर्गम (4, 3) (4, 1)
012,आदि ....
संपादित करें, यह संभव है वास्तव में
के बाद से JoshD सही ढंग से कहा गया है कि हम तत्वों की संख्या के लिए देख रहे हैं, तो आप एक बी पेड़ एक ढेर के बजाय का उपयोग कर सकते हैं और फिर आप बस की गिनती प्राप्त कर सकते हैं मौजूदा आइटम से कम तत्व और इसे काउंटर में जोड़ें।
यह उन सटीक जोड़े के लिए नहीं पूछ रहा है जो उलट रहे हैं, केवल ऐसे जोड़े की कुल गणना। – JoshD
@ जोशड, उस स्थिति में, इस एल्गोरिदम का उपयोग ओ (एन लॉग एन) प्राप्त करने के लिए किया जा सकता है। आपको केवल एक डेटा संरचना का उपयोग करने की आवश्यकता है जिसमें ओ (लॉग एन) में जोड़े गए आइटम हो सकते हैं और जो ओ (लॉग एन) समय में थ्रेसहोल्ड के नीचे आइटम की संख्या प्राप्त कर सकते हैं। एक बी-पेड़ यह कर सकता है, लेकिन एक ढेर से लागू करना मुश्किल है। – tster
इसे एक बाइनरी खोज पेड़ बनाकर हल किया जा सकता है जैसे कि प्रत्येक नोड में इसके बाएं उप-आकार का आकार होता है।
मूल सरणी के विपरीत क्रम में बीएसटी में मान जोड़े गए हैं। एक योग रखा जाता है और जब भी हम नोड जोड़ते समय सही होते हैं, तो वर्तमान नोड को बाएं उपट्री + 1 के आकार की तुलना में अंतिम योग में जोड़ा जाता है (चूंकि मान जोड़ा जा रहा है उस नोड से अधिक है और इसके बाईं ओर प्रत्येक मान सबट्री)।
पेड़ का निर्माण करना ज्ञात है और एक बार पेड़ बनने के बाद, योग जोड़े की संख्या होगी।
विशेष जरूरतों से निपटने आवश्यकताओं के आधार पर डुप्लिकेट संख्या के लिए जोड़े जाने के लिए (यानी (4,3) दो बार दिखाई देता है, तो यह दो बार गिना जाना चाहिए)
दाएँ से बाएँ ट्रेवर्सल, लाल काला पेड़ जहां प्रत्येक नोड को इसके संबंधित उप-आकार के आकार से बढ़ाया जाता है। इसलिए किसी दिए गए तत्वों की संख्या को खोजने के लिए ओ (लॉगऑन) लगता है।
@ jlewis42 बताते हैं, आप मर्ज सॉर्ट के एक संशोधित संस्करण का उपयोग कर सकते हैं। मैं बस जोड़ना चाहता था, आप किसी भी मानक comparison sort एल्गोरिदम का उपयोग कर सकते हैं, जब तक कि सबसे खराब केस चलने का समयहै, इसे "उपकरण" द्वारा उलटा गिनने के लिए यह काम करता है। डुप्ले के पास this भी देखें।
आपने उन्हें क्या बताया? उन्होने तुम्हे क्या कहा? – tster
मैंने ओ (एन^2) 2 लूप के साथ सोलन दिया। उन्होंने कहा कि एक ओ (nlogn) एक – Nemo
है http://stackoverflow.com/questions/337664/counting-Inversions-in-an-array? – Rsh