ओ (एन) समय

Question

में किसी सरणी में डुप्लिकेट खोजें ओ (एन) समय में एन तत्वों की सरणी में सभी डुप्लिकेट तत्वों को खोजने का कोई तरीका है?

उदाहरण:

इनपुट: 11, 29, 81, 14, 43, 43, 81, 29

आउटपुट: 29, 81, 43

इनपुट छंटाई और डुप्लिकेट का पता लगाने के एक रेखीय स्कैन करने के क्रम नष्ट कर देता है और उत्पादन देता है: 29,43,81।

छंटाई-दर-कुंजी सूचकांकों का एक और सरणी {0,1,...N-1} दिया सरणी के अनुसार {1,4,2} पाने के लिए और उसके बाद सूचकांकों की परिणामी सेट छँटाई पाने के लिए {1,2,4} हमें {29,81,43} दे देंगे, लेकिन इस O(N logN) समय लगता है।

क्या इस समस्या को हल करने के लिए ओ (एन) एल्गोरिदम है?

पीएस मैं जोड़ना भूल गया: मैं हैश टेबल का उपयोग नहीं करना चाहता। मैं एक गैर-हैश समाधान की तलाश में हूं।

Answer 1

मेरा मानना ​​है कि एक अच्छा समाधान (सभ्य स्मृति उपयोग, का उपयोग तुरंत यह निर्धारित करने के लिए किया जा सकता है कि एक प्रविष्टि पहले से ही आदेश को संरक्षित कर रही है, और एक रैखिक जटिलता के साथ) a trie है।

आप trie में तत्वों को सम्मिलित हैं जैसे कि वे प्रत्येक अंक प्रत्येक नोड में (एमएसडी से शुरू) के साथ एक स्ट्रिंग थे, तो आप इस हे की एक जटिलता (मीटर एन) जहां मीटर के साथ बंद खींच सकते हैं आधार -10 अंकों में संख्याओं की औसत लंबाई है।

आप बस अपनी सभी प्रविष्टियों पर लूप करेंगे और उन्हें ट्राई में डालेंगे। प्रत्येक बार जब कोई तत्व पहले से मौजूद होता है, तो आप इसे छोड़ देते हैं और अगले पर जाते हैं। इसमें डुप्लिकेट (एक रेडिक्स सॉर्ट के पिछले जवाब के विपरीत) अंतिम पुनरावृत्ति के बजाय तत्काल पाए जाएंगे या नहीं।

मुझे यकीन नहीं है कि आपको यहां एक प्रत्यय पेड़ का उपयोग करने से लाभ होगा, क्योंकि त्रिभुज में प्रवेश किए जा रहे पात्रों के "आधार" केवल 10 (एएनएसआई तारों के लिए बेस-128 की तुलना में) है, लेकिन यह है मुमकिन।

Answer 2

यदि आपके इनपुट सभी छोटे पूर्णांक हैं तो आप counting sort का उपयोग कर सकते हैं जो ओ (एन) समय में चलता है और ओ (एम) स्पेस की आवश्यकता होती है जहां मीटर संभावित इनपुट की सीमा का आकार होता है।

एक स्पेस ऑप्टिमाइज़ेशन के रूप में यह थोड़ा सरणी का उपयोग करने के लिए पर्याप्त है और यह स्टोर करने के लिए एक बिट (बजाय गिनती के बजाय) का उपयोग करने के लिए पर्याप्त है कि आपने उस आइटम को पहले या नहीं देखा है या नहीं।

Answer 3

आप अधिकतम मूल्य आप इस तरह कर सकते हैं पता है,
डुप्लीकेट खोजना बस के रूप में कठिन है छँटाई के रूप में अधिकतम मूल्य

int[max] secondarray; 

    for(int i=o;i<arrayFirst.length;i++){ 
     if(secondarray[arrayFirst[i]]==0){ 
      secondarray[arrayFirst[i]]==arrayFirst[i]; 
     }else{ 
      result.add(arrayFirst[i]); 
      } 
    } 

Answer 4

के रूप में लंबाई के साथ एक अलग सरणी है। ओ (एन) सॉर्ट प्राप्त करने के लिए आपकी सर्वश्रेष्ठ शर्त आपके इनपुट की कुछ संपत्ति का शोषण कर रही है।

Answer 5

ऐसा लगता है कि आप किसी भी अतिरिक्त स्थान आवंटित करने के प्रतिकूल हैं। फिर भी, एक हैश टेबल अभी भी गति के लिए सही समाधान है। ईमानदारी से, सरल डेटा के लिए अधिकांश हैश टेबल कार्यान्वयन जैसे कि पूर्णांक उनके एक-समाधान-फिट से बहुत अधिक वजन वाले होते हैं-सभी प्रकृति जिन्हें मैं अपनी जरूरतों के आधार पर अपना खुद का रोल करता हूं। यह धीमी कोड को तेज़ कोड में बदल सकता है जब आपको अपेक्षाकृत कम काम के लिए इसकी आवश्यकता होती है।

इसके अलावा, अगर टेबल हैश करने के लिए अपनी आपत्ति है कि वे तो शायद आदेश को नष्ट आप उन्हें थोड़ा अलग तरह से उपयोग करने की उम्मीद हे (एन) प्राप्त करने के लिए, जबकि व्यवस्था बनाए रखने कर सकते हैं:

एक हैश तालिका नक्शे कि अपना सरणी तत्वों को गिनती क्षेत्र के रूप में दो बिट्स में शून्य से तीन तक, और तत्वों की सरणी में सूचकांक के रूप में तीस बिट्स। जब तक आपके सरणी में अरबों मूल्य नहीं मिलते हैं, तब तक तीस बिट पर्याप्त नहीं होते हैं। इस तरह आपके हैश मान केवल 32-बिट शब्द हैं।

सरणी में तत्वों के माध्यम से जाएं। यदि कोई तत्व तालिका में नहीं है, तो मान हैश तालिका में मान डालें और गिनती फ़ील्ड को शून्य पर सेट करें। इससे कोई फर्क नहीं पड़ता कि जब आप इसे स्टोर करते हैं तो इंडेक्स भाग क्या होता है। यदि तत्व तालिका में है और गिनती फ़ील्ड शून्य है, तो इसे 1 तक बढ़ाएं और तत्व सूचकांक को नए गिनती फ़ील्ड मान के साथ स्टोर करें। यदि गिनती फ़ील्ड पहले से एक या अधिक है, तो इसे दो पर सेट करें और संग्रहीत अनुक्रमणिका को स्पर्श न करें - इसे छोड़ दें।

फिर से सरणी में तत्वों के माध्यम से जाएं।प्रत्येक तत्व को देखो और यदि इसकी अनुक्रमणिका एक संग्रहित है और संबंधित गिनती फ़ील्ड शून्य से अधिक है, तो इसे प्रिंट करें।

यह आपको ओ (एन) समय के साथ उचित क्रम में जो चाहिए, उसे प्राप्त करना चाहिए। लेकिन, यह हैश टेबल का उपयोग करता है जो अज्ञात कारण के लिए वांछित नहीं हैं। मैं अत्यधिक अनुशंसा करता हूं कि आप या तो इस तरह के समाधान को स्वीकार करें या सीमाओं की व्याख्या करें ताकि आपको अधिक सटीक लक्षित समाधान मिल सके।

Answer 6

आप इसे ओ (एन) में कर सकते हैं, हालांकि यह सरणी को पूर्णांक की आवश्यकता होगी। इसके लिए आवश्यक स्थान ऑर्डर आकार -2^32 से 2^32 के बावजूद हो सकता है। आपको क्या करना होगा मूल सरणी (सरणी) का अधिकतम और न्यूनतम पाएं। फिर दो सरणी (सरणी +) और (arraynew-) बनाओ।

यदि सरणीग में सभी मान हैं तो (arraynew +) का आकार अधिकतम (arrorig) -min (arrayorig) होगा, अन्यथा (arraynew +) का आकार अधिकतम (सरणी) होगा।

आकार (सरणी-) शून्य होगा यदि सभी मान सकारात्मक हैं, अन्यथा वे न्यूनतम (सरणी) के पूर्ण मूल्य के बराबर होंगे।

फिर आप सरणीग पर पुनरावृत्त कर सकते हैं और मूल्य को 1 (arraynew-) या (arraynew +) द्वारा arraorig के मान से संबंधित सूचकांक में बढ़ा सकते हैं, यदि मान सकारात्मक वृद्धि को (arraynew +) पर किया जाना चाहिए यदि इसकी ऋणात्मक वृद्धि (सरणी-) की अनुक्रमणिका (arraynew-) पर की जानी चाहिए जो सरणी के पूर्ण मूल्य के बराबर है। तब सभी की (arraynew +) और अनुक्रमित ((arraynew-) मूल्य के साथ> 1 arrayorig की अलग-अलग मान रहे हैं।

Answer 7

void printRepeating(int arr[], int size) 
{ 
int i; 
    printf("The repeating elements are: \n"); 
for (i = 0; i < size; i++) 
{ 
if (arr[abs(arr[i])] >= 0) 
    arr[abs(arr[i])] = -arr[abs(arr[i])]; 
else 
    printf(" %d ", abs(arr[i])); 
} 
    }