अज्ञात आकार सूची के बीच

Question

हाल ही में एक साक्षात्कार में मैंने पूछा था खोजें:

पहले की स्थिति से शुरू अज्ञात लंबाई का एक क्रमबद्ध सूची के बीच तत्व का पता लगाएं।

मैं इस के साथ जवाब दिया:

2 की स्थिति काउंटर है: जब काउंटर 2 सूची काउंटर के अंत तक पहुँच जाता है

counter1 counter2

1 से और 2 से counter2 वृद्धि counter1 1 होगा बीच में रहो मुझे लगता है कि यह कुशल नहीं है क्योंकि मैं पहले से देखे गए नोड्स की समीक्षा कर रहा हूं। किसी भी तरह से, क्या एक और अधिक कुशल एल्गोरिदम है?

Answer 1

एक लिंक्ड सूची मानते हुए, आप वस्तुओं के मनमाने ढंग से-नज़दीकी से मिलने के दौरान इसे कर सकते हैं।

ऐसा करने के लिए 5/4 N: सूची पर

• दोहराएं जब तक आप अंत मारा, आइटम की गिनती।
• 2'th तत्व की प्रत्येक शक्ति पर एक एंकर ड्रॉप करें। पिछले 2 एंकरों को ट्रैक करें।
• पहले-आखिरी एंकर को तब तक घुमाएं जब तक यह सूची के बीच तक नहीं पहुंच जाता।

जब आप सूची के अंत को दबाते हैं, तो पहले-आखिरी एंकर मध्य बिंदु से पहले होता है लेकिन कम से कम आधे रास्ते पहले से ही होता है। तो पूर्ण पुनरावृत्ति के लिए एन + एंकर = 5/4 एन

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

Answer 2

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

फिर, स्थिति END_OF_LIST/2.

इस तरह की तलाश है, तो आप प्रत्येक नोड यात्रा करने के लिए नहीं है।

Answer 3

मुझे लगता है कि आप एक लिंक-सूची पर चर्चा कर रहे हैं। वास्तव में आपका समाधान एक उत्कृष्ट है। एक विकल्प केवल तत्वों की संख्या की गणना करने वाली सूची को पार करना होगा, और फिर शुरुआत से शुरू करना होगा, गिनती राशि का आधा हिस्सा। दोनों विधियां 3n/2 नोड्स को पार करते हैं, इसलिए इसमें कोई फर्क नहीं पड़ता है।

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

Answer 4

तकनीकी रूप से, यदि आप ओ (एन) स्मृति का उपयोग करते हैं (मान लीजिए कि आप एक लिंक्ड सूची का उपयोग कर रहे हैं) तो आप इसे एक ट्रैवर्सल में कर सकते हैं।

1. सूची को ट्रैक करें और इसे एक सरणी में परिवर्तित करें (पॉइंटर्स के अगर यह एक लिंक की गई सूची है)।
2. वापसी आगमन [एन/2]

संपादित करें: मैं अपने जवाब हालांकि प्यार करते हो!

Answer 5

नियमित में स्मृति लिंक्ड सूची है कि वर्तमान में कई बार के संदर्भ में दिए गए अगले तत्व पढ़ने की अनुमति देता है मान लिया जाये कि (त्याग, परीक्षण नहीं किया, लेकिन यह विचार काम करना चाहिए):

// assume non-empty list 
slow = fast = first; 
count = 0; 

while (fast) 
{ 
    fast = fast.next; 

    if (!fast) 
    break; 

    count++; 
    fast = fast.next; 

    if (fast) 
    count++; 

    slow = slow.next; 
} 

if (count % 2) 
    return slow.data; 
else 
    return (slow.data + slow.next.data)/2.0; 

एक और अधिक कठिन मामला वह तब होता है जब "सूची" स्मृति में एक लिंक्ड सूची नहीं है, बल्कि एक धारा जिसे आप क्रमबद्ध क्रम में पढ़ सकते हैं और प्रत्येक तत्व को केवल एक बार पढ़ना है जिसके लिए मेरे पास कोई अच्छा समाधान नहीं है।