In Place Duplicates हटाना

दिए गए क्रमबद्ध ऐरे में बिना किसी अतिरिक्त ऐरे के हर मान की एक प्रति रखें। स्थान पर काम करने से मेमोरी बचती है और यह साक्षात्कारों में पूछा जाने वाला एक सामान्य प्रश्न है। 🧹

जब ऐरे क्रमबद्ध होता है, तो हर दोहराया हुआ मान अपने समान मान के ठीक बगल में होता है। इसलिए आपको पूरे ऐरे से नहीं, केवल पड़ोसी मानों से तुलना करनी पड़ती है।

एक धीमा पॉइंटर रखें, जो आखिरी सुरक्षित मान को दर्शाए, और एक तेज़ पॉइंटर रखें, जो आगे स्कैन करके नया मान खोजे।

धीमे पॉइंटर को लिखने की स्थिति समझें: उसके स्थान तक और उससे पहले की हर चीज़ पहले ही साफ़ और अद्वितीय है।

तेज़ पॉइंटर केवल आगे पढ़ता है। वह आगे बढ़ता रहता है और जब उसे अभी तक सुरक्षित न किया गया मान मिलता है, तभी धीमे पॉइंटर को संकेत देता है।

यदि a[fast], a[slow] के बराबर है, तो वह दोहराव है। इसलिए तेज़ पॉइंटर को आगे बढ़ाने के अलावा कुछ न करें। दोहराया हुआ मान चुपचाप पार हो जाएगा।

जब a[fast] अलग हो, तो धीमे पॉइंटर को आगे बढ़ाएँ और नया मान वहाँ कॉपी करें। इससे पुराने दोहराव नए अद्वितीय डेटा से बदल जाते हैं।

स्कैन के बाद slow + 1 अद्वितीय मानों की संख्या होती है, जो सभी ऐरे के आरंभ में एक साथ रखे होते हैं।

अद्वितीय प्रारंभिक भाग के बाद जो कुछ भी है, वह बचा हुआ अनावश्यक डेटा है। समस्या केवल पहले slow + 1 तत्वों से संबंधित है, इसलिए अंतिम भाग को वैसा ही छोड़ दें।

एक खाली ऐरे में अद्वितीय मानों की संख्या शून्य होती है। शुरू करने से पहले n == 0 की जाँच करें, ताकि अंत से आगे पढ़ने की कोशिश न हो।

यह धीमा-तेज़ तरीका O(n) समय और O(1) अतिरिक्त स्थान में चलता है, जो कड़ी मेमोरी सीमाओं के लिए बिल्कुल उपयुक्त है।

क्रमबद्ध ऐरे में धीमे-तेज़ पॉइंटरों की जोड़ी बिना अतिरिक्त स्थान के एक O(n) पास में दोहराव हटा देती है और अद्वितीय मानों की संख्या के रूप में slow + 1 लौटाती है। 🎉