डबली लिंक्ड सूची से डुप्लिकेट हटाएं

Question

हैलो मैंने निम्नलिखित प्रश्न को ठोकर दिया है आपने दोबारा जुड़ी लिंक वाली सूची दी है। आपको डुबकी से जुड़ी सूची से डुप्लिकेट ढूंढना और हटाना चाहिए।

न्यूनतम एल्गोरिदमिक जटिलता के साथ ऐसा करने का सबसे अच्छा तरीका क्या है?

धन्यवाद।

Answer 1

यदि स्थान प्रचुरता है और आपको इसे समय के साथ वास्तव में अनुकूलित करना है, तो शायद आप Hashset (या सी ++ में समकक्ष) का उपयोग कर सकते हैं। आप प्रत्येक तत्व को पढ़ते हैं और इसे हैशसेट पर दबाते हैं। यदि हैशसेट एक डुप्लिकेट की रिपोर्ट करता है, तो इसका मतलब है कि एक डुप्लिकेट है। आप बस उस नोड को हटा देंगे।

जटिलता एक दोगुना लिंक्ड सूची दो अकेले जुड़ा हुआ सूचियों के बजाय के रूप में यह की O(n)

Answer 2

न्यूनतम जटिलता के साथ? सूची में नीचे X बार तक सूची को पार करें (जहां एक्स आइटम की संख्या है), फिर सिर से शुरू करें और फिर सूची के नीचे (और पॉइंटर्स को फिर से असाइन करें) हटाएं। ओ (एन लॉग एन) (मुझे विश्वास है) खराब मामले में समय, और कोड के लिए वास्तव में आसान है।

Answer 3

लगता है, पिछले करने के लिए पहले जा रहा लिंक का एक सेट और एक और सेट पहले करने के लिए पिछले जा रहा है। आप दूसरी सूची को मर्ज सॉर्ट के साथ सॉर्ट कर सकते हैं, जो ओ (एन लॉग एन) होगा। अब पहले लिंक का उपयोग कर सूची को पार करें। प्रत्येक नोड के लिए, (node.back)->key==node.key जांचें और यदि ऐसा है तो इसे सूची से हटा दें। इस ट्रैवर्सल के दौरान बैक पॉइंटर को पुनर्स्थापित करें ताकि सूची ठीक से दोगुनी हो।

यह आवश्यक रूप से सबसे तेज़ तरीका नहीं है, लेकिन यह किसी भी अतिरिक्त स्थान का उपयोग नहीं करता है।

Answer 4

यह मानते हुए कि संभावित नियोक्ता सी ++ पुस्तकालय में विश्वास रखता है:

// untested O(n*log(n)) 
temlate <class T> 
void DeDup(std::list<T>& l) { 
    std::set<T> s(l.begin(), l.end()); 
    std::list<T>(s.begin(), s.end()).swap(l); 
}