किसी दिए गए सरणी में सबसे लंबी दूरी वाला तत्व ढूंढें जहां प्रत्येक तत्व दो बार प्रकट होता है?

Question

int की एक सरणी को देखते हुए, प्रत्येक int सरणी में बिल्कुल TWICE दिखाई देता है। int को ढूंढें और वापस करें जैसे कि int की इस जोड़ी में अधिकतम इस सरणी में एक-दूसरे के बीच की दूरी है।

उदा। [2, 1, 1, 3, 2, 3]

2: d = 5-1 = 4; 
1: d = 3-2 = 1; 
3: d = 6-4 = 2; 
return 2 

मेरे विचार:

hashmap का प्रयोग करें, कुंजी a[i] है, और मूल्य सूचकांक है। a[] स्कैन करें, प्रत्येक नंबर को हैश में रखें। यदि कोई संख्या दो बार मारा जाता है, तो इसके सूचकांक को पुरानी संख्या सूचकांक से कम करें और हैश में तत्व मान को अद्यतन करने के लिए परिणाम का उपयोग करें।

उसके बाद, हैश स्कैन करें और कुंजी को सबसे बड़ा तत्व (दूरी) के साथ वापस कर दें। यह समय और स्थान में ओ (एन) है।

ओ (एन) समय और ओ (1) अंतरिक्ष में इसे कैसे करें?

Answer 1

आप अधिकतम दूरी चाहते हैं, तो मुझे लगता है कि आप जिस नंबर को खोजते हैं, वह आरंभ और अंत में होने की संभावना है। यही कारण है कि मैं एक ही समय में शुरुआत और अंत से सरणी पर लूप होगा।

[2, 1, 1, 3, 2, 3] 
Check if 2 == 3? 
Store a map of numbers and position: [2 => 1, 3 => 6] 
Check if 1 or 2 is in [2 => 1, 3 => 6] ? 

मुझे पता है, यह छद्म कोड भी नहीं है और पूरा नहीं है बल्कि विचार देने के लिए है।

Answer 2

पहले तत्व में iLeft अनुक्रमणिका सेट करें, iRight अनुक्रमणिका दूसरे तत्व के लिए सेट करें। वृद्धि iRight अनुक्रमणिका जब तक आपको बाएं आइटम की एक प्रति न मिल जाए या सरणी के अंत को पूरा न करें। पहले मामले में - दूरी याद रखें।

वृद्धि iLeft। नए iRight से खोजना शुरू करें। iRight का प्रारंभ मूल्य कभी कम नहीं होगा। डेल्फी कोड:

iLeft := 0; 
    iRight := 1; 

    while iRight < Len do begin //Len = array size 
    while (iRight < Len) and (A[iRight] <> A[iLeft]) do 
     Inc(iRight); //iRight++ 
    if iRight < Len then begin 
     BestNumber := A[iLeft]; 
     MaxDistance := iRight - iLeft; 
    end; 
    Inc(iLeft); //iLeft++ 
    iRight := iLeft + MaxDistance; 
    end; 

Answer 3

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

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

हैशैप सेल में सरणी तत्व बदलने से पहले, इसकी मान और स्थिति याद रखें। इसके बाद इसे सुरक्षित रूप से ओवरराइट किया जा सकता है। फिर हैशैप में एक नई स्थिति की गणना करने और इसे ओवरराइट करने के लिए इस मान का उपयोग करें। एक खाली सेल मिलने तक तत्व इस तरह से shuffled हैं। जारी रखने के लिए, किसी भी तत्व का चयन करें, जो पहले से ही पुन: व्यवस्थित नहीं है। जब सबकुछ फिर से व्यवस्थित होता है, तो प्रत्येक इंट जोड़ी निश्चित रूप से दो बार हिट होती है, यहां हमारे पास एक खाली हैशैप है और एक अद्यतन सर्वोत्तम परिणाम मूल्य है।

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

2 और आरक्षित बिट्स का प्रयोग विवादित मूल्यों को श्रृंखलाबद्ध करने के लिए किया जाता है। वे पदों को एन्कोड करते हैं जहां श्रृंखला शुरू/समाप्त/जारी होती है। (यह एल्गोरिदम अनुकूलित करना संभव हो सकता है ताकि केवल 2 आरक्षित बिट्स की आवश्यकता हो ...)

एक हैशैप सेल में इन 3 आरक्षित बिट्स, मूल मूल्य सूचकांक और कुछ तत्वों को विशिष्ट रूप से इस तत्व की पहचान करने के लिए होना चाहिए। इसे संभव बनाने के लिए, हैश फ़ंक्शन को उलट दिया जाना चाहिए ताकि मान का हिस्सा तालिका में अपनी स्थिति के अनुसार बहाल किया जा सके। सबसे सरल मामले में, हैश फ़ंक्शन केवल ceil(log(n)) कम से कम महत्वपूर्ण बिट्स है। तालिका में मान 3 क्षेत्रों के होते हैं: मूल मूल्य से

32 - 3 - (ceil(log(n))) उच्च आदेश बिट

• 3 आरक्षित बिट्स मूल सरणी

समय जटिलता में तत्व की स्थिति के लिए

ceil(log(n)) बिट्स ओ (एन) केवल औसत पर है; सबसे खराब मामला जटिलता ओ (एन^2) है।

इस एल्गोरिदम का अन्य संस्करण सरणी को क्रमशः हैशैप में बदलने के लिए है: प्रत्येक चरण m पर 2^m हैशैप में परिवर्तित सरणी के पहले तत्व हैं। m कम होने पर प्रदर्शन को बेहतर बनाने के लिए कुछ स्थिर आकार वाले सरणी को हैशैप के साथ इंटरलीव किया जा सकता है। जब m ऊंचा है, वहां पर्याप्त int जोड़े होना चाहिए, जो पहले ही संसाधित हो चुके हैं, और अब स्पेस की आवश्यकता नहीं है।

Answer 4

ओ (एन) समय और ओ (1) अंतरिक्ष में ऐसा करने का कोई तरीका नहीं है।