सूची में कौन सा पूर्णांक गुम होने की गणना करने का सबसे अच्छा तरीका क्या है?

Question

मैं हाल ही में एक साक्षात्कार में था जहां उन्होंने मुझे तकनीकी प्रश्न पूछे। एक यह था कि आप कैसे गणना करेंगे कि लंबाई एन -1 की सूची में कौन सा नंबर गुम था। सूची में 1 से n तक प्रत्येक नंबर शामिल है, सिवाय इसके कि मैं कहां 1 < = i < = n। संख्या क्रम में नहीं थी। मेरा समाधान उन सभी को जोड़ना था, फिर 1 से एन तक संख्याओं की गणना से, 1 से एन जोड़कर और एन/2 या (एन -1)/2 द्वारा गुणा करके उचित रूप से घटाएं। लेकिन मुझे समझ में आया कि ऐसा करने का एक बेहतर तरीका था। इष्टतम समाधान क्या है?

Answer 1

आपकी राय मेरी राय में काफी अच्छी है।

लेकिन कुछ लोग - शायद आपका साक्षात्कारकर्ता उनमें से एक है - अतिप्रवाह और इस तरह के बारे में चिंतित हैं। उस स्थिति में, अतिरिक्त के बजाय एक्सओआर का उपयोग करें।

एन 0 से पूर्णांकों का XOR प्राप्त करने के लिए, बस XOR एक साथ आप लूप के रूप में सरणी सूचकांक। 0 से एन के पूर्णांक के एक्सओआर और सरणी तत्वों के एक्सओआर को देखते हुए, आप गायब तत्व प्राप्त करने के लिए उन दोनों में से एक को एक्सओआर करते हैं।

पीएस 1 से n तक पूर्णांक का योग हमेशा (एन + 1) * एन/2

Answer 2

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

Answer 3

आपकी विधि बिल्कुल ठीक है। यह अंतरिक्ष और समय दोनों के मामले में इष्टतम है। ओवरफ्लो इसके साथ एकमात्र समस्या हो सकती है।

एक और संभावित विधि हैशसेट का उपयोग कर सकती है। प्रारंभिक हैशसेट बनाएं जिसमें मान 1-> एन है। अब सूची में आने वाले प्रत्येक नंबर के लिए - हैशसेट से उस मान को हटाएं। अंत में, हैशसेट में मौजूद मान गुम मूल्य है।

यह विधि समय और अंतरिक्ष जटिलता में ओ (एन) है। आपकी विधि (अतिप्रवाह को छोड़कर) समय में ओ (एन) और ओ (1) जटिलता थी। अंतरिक्ष के लिए जोड़ा 'एन' कारक ओवरफ्लो को खत्म करने की लागत है।

Answer 4

आपका समाधान के रूप में @Nemo एन 1 से पूर्णांकों का योग बताते हैं, एक परिवर्तन के साथ काफी इष्टतम है हमेशा (n+1) * n/2

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

आप अतिप्रवाह बारे में चिंतित हैं, और अपने मूल्यों (सबसे .Length मूल्यों सरणियों शामिल कर रहे हैं के रूप में) तो सिर्फ एक int64 के रूप में योग की दुकान हमेशा int32 कर रहे हैं, सभी सकारात्मक पूर्णांक की राशि को महत्व देता (((long)int.MaxValue) +1L) * (int.MaxValue/2) = 2305843007066210304 जो अभी भी फिट करने में सक्षम है .MaxValue = 9223372036854775807 के साथ int64 के भीतर।

दूसरों द्वारा उल्लिखित अन्य उत्तर प्रत्येक आइटम को एक्सओआर करना है और एक एक्सओआर चलाना है, लेकिन फिर आपको O(1) समय में अपेक्षित कुल एक्सओआर प्राप्त करने के लिए एक फॉर्मूला तैयार करने की आवश्यकता है।

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

आगे कोड में अपने समाधान में सुधार करने के लिए, सरणी के बजाय सूचकांक मूल्य (यदि आपके कोड है सी # एक उचित सुधार किया जाएगा जो) तक पहुँचने के लिए एक सूचक का उपयोग करने के लिए होगा।