सरणी में एक गैर-दोहराव तत्व खोजें?

Question

मेरे पास n तत्वों की एक सरणी है जिसमें केवल एक तत्व दोहराया नहीं जाता है, अन्य सभी नंबर दोहराए जाते हैं> 1 बार। और सरणी में संख्याओं की सीमा पर कोई सीमा नहीं है।

कुछ समाधान हैं:

• हैश, का प्रयोग करने वाले लेकिन यह है कि रैखिक समय जटिलता लेकिन बहुत गरीब अंतरिक्ष जटिलता
• में परिणाम होगा सूची MergeSort O(nlogn) का उपयोग कर छंटाई और फिर तत्व की खोज जो

दोहराना नहीं है क्या कोई बेहतर समाधान है?

Answer 1

एक सामान्य दृष्टिकोण एक बाल्टी तकनीक (जिसमें हैशिंग ऐसी तकनीक है) को लागू करने के लिए तत्वों को अपनी पहचान (इंडेक्स कहें) का उपयोग करके विभिन्न "बाल्टी" में वितरित करने के लिए है और फिर बाल्टी को सबसे छोटे आकार (1 में आपका मुकदमा)। मुझे विश्वास है कि यह समस्या अल्पसंख्यक तत्व समस्या के रूप में भी जाना जाता है। आपके सेट में अद्वितीय तत्व होने के कारण कई बाल्टीयां होंगी।

हैशिंग द्वारा ऐसा करना टकराव की वजह से समस्याग्रस्त है और आपका एल्गोरिदम कैसा संभाल सकता है। प्रयास और विस्तार योग्य हैशिंग जैसे कुछ सहयोगी सरणी दृष्टिकोण लागू नहीं होते हैं क्योंकि वे स्ट्रिंग के लिए बेहतर अनुकूल होते हैं।

उपरोक्त का एक आवेदन Union-Find data structure पर है। आपके सेट बाल्टी होंगे और आपको $ O (\ alpha (n)) $$ की लागत के लिए अपनी सरणी में प्रत्येक तत्व के लिए मेकसेट() और ढूँढें() को कॉल करने की आवश्यकता होगी, जहां $ \ alpha (n) $ बेहद धीमी बढ़ती व्यस्त एकरमेन समारोह है। आप इसके बारे में प्रभावी रूप से स्थिर होने के बारे में सोच सकते हैं।

जब कोई तत्व पहले से मौजूद है तो आपको संघ करना होगा। न्यूनतम कार्डिनालिटी के साथ सेट का ट्रैक रखने के लिए कुछ बदलावों के साथ, इस समाधान को काम करना चाहिए। इस समाधान की समय जटिलता $ ओ (एन \ अल्फा (एन)) $ है।

आपकी समस्या Element Uniqueness problem से कम से कम प्रतीत होती है।

Answer 2

यदि आपके पास सख्त स्पेस सीमा है तो बहु-पास स्कैनिंग आज़माएं।

कहें इनपुट में एन तत्व हैं और आप केवल अपनी स्मृति में एम तत्वों को पकड़ सकते हैं। यदि आप हैश-टेबल दृष्टिकोण का उपयोग करते हैं, तो सबसे बुरे मामले में आपको n/2 अद्वितीय संख्याओं को संभालने की आवश्यकता है ताकि आप m> n/2 चाहते हैं। यदि आपके पास वह बड़ा मीटर नहीं है, तो आप n तत्वों को k = (अधिकतम (इनपुट) -min (इनपुट))/(2m) समूहों में विभाजित कर सकते हैं, और आगे बढ़ें एन इनपुट तत्वों के समय स्कैन करें (सबसे खराब में मामला):

पहला रन: आप केवल 0hन्यूनतम (इनपुट) + एम * 2 के साथ जो भी तत्व हैंश-प्राप्त/डाल/चिह्न/क्योंकि सीमा में (न्यूनतम (इनपुट), न्यूनतम (इनपुट) + एम * 2) अधिकांश एम अद्वितीय तत्व हैं और आप इसे संभाल सकते हैं। यदि आप भाग्यशाली हैं तो आपको पहले से ही अद्वितीय मिल जाएगा, अन्यथा जारी रखें।

2 रन: केवल रेंज में मूल्य के साथ तत्वों पर कार्य करते हैं (न्यूनतम (इनपुट) + m * 2, न्यूनतम (इनपुट) + m * 4), और इतने पर है, इसके आगे

इस तरह, यदि आप एक हे (केएन) के लिए समय जटिलता समझौता, लेकिन आप एक अंतरिक्ष जटिलता हे (एम) के लिए बाध्य मिल

Answer 3

दो विचारों मेरे मन के लिए आते हैं:

• एक smoothsort तुलना में एक बेहतर विकल्प हो सकता है आपकी जरूरतों के लिए उद्धृत विलय को यह ओ (1) स्मृति उपयोग में दिया गया है, ओ (nlogn) सबसे खराब कैस में ई मर्ज सॉर्ट के रूप में लेकिन ओ (एन) सर्वोत्तम मामले में;

• (विपरीत) splay tree के विचार के आधार पर, आप एक प्रकार का वृक्ष है कि नीचे की ओर लीफ़्स धक्का होगा एक बार वे (टेढ़ा पेड़ में के रूप में ऊपर की ओर के बजाय) उपयोग किया जाता है बना सकते हैं। यह आपको अभी भी एक ओ (nlogn) प्रत्यारोपण प्रदान करेगा, लेकिन लाभ अद्वितीय तत्व खोजने का ओ (1) कदम होगा, यह रूट होगा। छँटाई एल्गोरिथ्म हे (nlogn) + O (एन) का योग है और इस एल्गोरिथ्म हे (nlogn) होगा + O (1)

अन्यथा, आप कहा गया है, एक हैश आधारित समाधान का उपयोग कर (के रूप में की तरह हैश-कार्यान्वित सेट) के परिणामस्वरूप ओ (एन) एल्गोरिदम (ओ (एन) को अनन्य तत्व ढूंढने के लिए अपने सेट को पार करने के लिए एक गिनती संदर्भ डालने और जोड़ने के लिए ओ (एन) होगा) लेकिन आपको स्मृति को नापसंद करना प्रतीत होता था उपयोग, हालांकि मुझे नहीं पता क्यों। मेमोरी सस्ता है, इन दिनों ...