डेटा संरचना

Question

पर एक पहेली मुझे कोडिंग प्रतियोगिता में puzzle प्रश्न [related to data structure] का सामना करना पड़ा।

पेड़ों का एक ग्रह है (असली पेड़ पेड़ डेटा संरचना नहीं !!)। इसमें अरबों या यहां तक ​​कि लाखों पेड़ हैं। राजा कार्बन डेटिंग का उपयोग करते हुए सभी पेड़ों के आयु (वर्षों और पूर्णांक में) के औसत को खोजने का आदेश देता है। (Method does not matter.) नोट: संख्याओं की क्रमबद्ध सूची में मध्य "मध्य संख्या" है।

प्रतिबंध:
1. सबसे पुराने पेड़ 2000 साल पुराना होने का जाना जाता है।
2. उनके पास एक मशीन है जो अनन्यता से + अनंत तक सीमा में पूर्णांक स्टोर कर सकती है।
3. लेकिन ऐसे पूर्णांक की संख्या जिसे एक समय में स्मृति में संग्रहीत किया जा सकता है 1 मिलियन है।

इसलिए, एक बार जब आप अगले स्टोर को स्टोर करने के लिए 1 मिलियन पूर्णांक स्टोर करते हैं तो आपको पहले से संग्रहीत एक को हटाना होगा।
तो किसी भी तरह उन्हें पेड़ों की उम्र गिनने के दौरान मध्यस्थ का ट्रैक रखना पड़ता है।
वे यह कैसे कर सकते हैं?

मेरे दृष्टिकोण
बाहरी प्रकार का एक संस्करण का उपयोग करें हिस्सा & उन्हें फाइल में लिखने में उम्र सॉर्ट करने के लिए।
के-रास्ता विलय [भाग के लिए] लागू करें।
उपरोक्त दृष्टिकोण के साथ समस्या यह है कि इसे फ़ाइल के दो स्कैन की आवश्यकता है।

मैं एक और दृष्टिकोण जो जानकारी The oldest tree is known to be 2000 years old.
हम नहीं ले सकते हैं एक count array [as range of ages of tree is fixed] का उपयोग करता है के बारे में सोच सकते हैं?

मुझे जानना है क्या कोई बेहतर तरीका है?
कोई भी तरीका है जहाँ हम फ़ाइल में डाटा स्टोर करने की जरूरत नहीं है वहाँ मौजूद है? [where only main memory is sufficient?]

Answer 1

तुम सिर्फ 2001 पूर्णांकों भंडारण के द्वारा यह कर सकता हूँ। विभिन्न संभावित उम्र

ages[2001] // [0..2000] 

की एक सरणी बनाएँ जब आप एक पेड़ गिनती

ages[thisAge]++ 

फिर कंप्यूटिंग मंझला तुच्छ है। आपने दूसरे समाधान में इस समाधान पर आपको मारा है, लेकिन फिर आप कहते हैं कि मैं जानना चाहता हूं कि कोई बेहतर दृष्टिकोण है?

किसी भी विधि वहाँ मौजूद है, जहां हम फ़ाइल में डाटा स्टोर करने की जरूरत नहीं है? [जहां केवल मुख्य स्मृति के लिए पर्याप्त है?]

मैं undertstand नहीं आता कि क्यों आप अगर पूछना वहाँ कोई भी विधि मौजूद है जहां मुख्य स्मृति पर्याप्त है। मुख्य स्मृति में 2001 पूर्णांक फिट की सरणी नहीं है?

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

Answer 2

आपके द्वारा अनुशंसित दृष्टिकोण (2001 साल की एक सरणी) ओ (एन) है, प्रति पेड़ एक तेज ऑपरेशन के साथ, यह इष्टतम है।

ठीक है, लगभग इष्टतम। गिनती के दौरान किसी बिंदु पर शेष पेड़ों की संख्या परिणाम बदलने के लिए अपर्याप्त होगी। उदाहरण के लिए, यदि मैं पेड़ के आधे + 1 की गिनती करता हूं, और सभी बिल्कुल 100 साल पुराने हैं, तो मेरा जवाब है: 100 साल।

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