ओ(एन) टाइम और ओ(1) स्पेस में डुप्लिकेट ढूंढना: एक गहन स्पष्टीकरण

समस्या में डुप्लिकेट की पहचान करना शामिल है किसी सरणी के भीतर तत्व जिनमें 0 से n-1 तक की संख्याएँ होती हैं। चुनौती इसे O(n) समय जटिलता के भीतर और केवल स्थिर (O(1)) मेमोरी स्पेस का उपयोग करके कुशलतापूर्वक प्राप्त करने में निहित है।

प्रस्तुत समाधान एक सरल तकनीक को नियोजित करता है जिसके लिए हैश टेबल या अन्य अतिरिक्त डेटा की आवश्यकता नहीं होती है संरचनाएँ। इसके बजाय, यह डुप्लिकेट तत्वों को पहचानने और चिह्नित करने के लिए सरणी में ही मानों का लाभ उठाता है। निम्नलिखित तर्क पर आधारित सरणी:

जबकि A[A[i]] != A[i] स्वैप(ए[आई], ए[ए[आई]]) अंत जबकि

1. यह क्रमपरिवर्तन चरण यह सुनिश्चित करता है कि यदि कोई तत्व x सरणी में मौजूद है, तो उसका कम से कम एक उदाहरण A[x] पर स्थित होगा। यह बाद के चरणों के लिए महत्वपूर्ण है। &&&]i के लिए := 0 से n - 1 यदि A[i] != मैं तो प्रिंट ए[i] समाप्त यदि अंत के लिएयदि A[i] != i, तो यह दर्शाता है कि i सरणी में अपने सही स्थान पर मौजूद नहीं है। इसलिए, यह एक डुप्लिकेट तत्व है, और यह मुद्रित है।

   while A[A[i]] != A[i]
       swap(A[i], A[A[i]])
   end while

   समय जटिलता विश्लेषण:

तकनीक O(n) समय में चलती है . नेस्टेड लूप में एक बाहरी लूप होता है जो n बार पुनरावृत्त होता है और एक आंतरिक लूप होता है जो अधिकतम n - 1 पुनरावृत्ति करता है (क्योंकि प्रत्येक स्वैप एक तत्व को उसकी सही स्थिति के करीब लाता है)। इस प्रकार, पुनरावृत्तियों की कुल संख्या n*(n - 1) से घिरी हुई है, जो O(n^2) है, लेकिन इसे n*(n - 1) = n^2 - n के रूप में O(n) तक सरल बनाया जा सकता है। = n(n - 1) = n*n - n
अंतरिक्ष जटिलता विश्लेषण:

for i := 0 to n - 1
    if A[i] != i then
        print A[i]
    end if
end for

डुप्लिकेट की उपस्थिति में भी समय जटिलता समान रहती है।

एल्गोरिदम छोटे से मध्यम आकार के सरणियों के लिए कुशल है। बड़े सरणियों के लिए, हैश टेबल जैसी डेटा संरचनाओं का उपयोग करने वाले वैकल्पिक दृष्टिकोण अधिक उपयुक्त हो सकते हैं।