पूर्णांक वाले सरणी में एक मान सरणी में दो बार होता है। आप कैसे निर्धारित करते हैं?

Question

मान लें कि सरणी में 1 और 1,000,000 के बीच पूर्णांक है।

मैं इस समस्या को हल करने के कुछ लोकप्रिय तरीके जानते हैं:

1. 1 और 1,000,000 के बीच सभी नंबरों को शामिल कर रहे हैं, सरणी तत्व की राशि मिल जाती है और कुल योग से घटा दें (n * n + 1/2)
2. एक हैश नक्शा (अतिरिक्त स्मृति की जरूरत है)
3. थोड़ा मैप का उपयोग करें (कम स्मृति भूमि के ऊपर)

मैं हाल ही में एक और समाधान में आए प्रयोग करें और मैं पीछे तर्क को समझने में कुछ मदद की ज़रूरत है यह:

एक एकल रेडिक्स संचयक रखें। आप अनन्य-या के साथ संचयक उस इंडेक्स पर इंडेक्स और मान दोनों।

तथ्य यह है कि x^सी^x == सी उपयोगी है, क्योंकि प्रत्येक नंबर दो बार xor'd होगा, जो दो बार वहां मौजूद है, जो 3 बार दिखाई देगा। (x^x^x == x) और अंतिम अनुक्रमणिका, जो एक बार दिखाई देगी। तो यदि हम अंतिम सूचकांक के साथ संचयक बीज करते हैं, तो संचयक का अंतिम मान सूची में दो बार होगा।

अगर कोई मुझे इस दृष्टिकोण के पीछे तर्क को समझने में मदद कर सकता है तो मुझे इसकी सराहना होगी (एक छोटे से उदाहरण के साथ!)।

Answer 1

मान लें कि आप एक संचायक

int accumulator = 0; 

अपने पाश की हर कदम पर है, तो आप i और v, जहां i पाश यात्रा के सूचकांक और v साथ संचायक XOR i वीं में मूल्य है सरणी की स्थिति। ताकि आप

accumulator ^= (i^i) 

लेकिन i^i == 0 कर खत्म हो जाएगा

accumulator ^= (i^v) 

आम तौर पर, i और v एक ही नंबर हो जाएगा, तो यह एक no-सेशन और संचायक का मूल्य जा रहा है खत्म हो जाएगा होगा छूटे रहो।इस बिंदु पर मुझे यह कहना चाहिए कि सरणी में संख्याओं का क्रम कोई फर्क नहीं पड़ता क्योंकि एक्सओआर कम्यूटिव है, इसलिए अगर अंत में परिणाम के साथ शुरू करने के लिए सरणी को घुमाया जाता है तो भी 0 (संचयक का प्रारंभिक मूल्य) होना चाहिए ।

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

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

int accumulator = N; 

के साथ शुरू है कि प्रभावी ढंग से N फिर XORing में दो बार दिखाई देता है। इस बिंदु पर, हमें संख्याओं के साथ छोड़ दिया गया है जो केवल दो बार दिखाई देते हैं, और केवल एक नंबर जो तीन बार दिखाई देता है। चूंकि दो बार दिखाई देने वाली संख्याएं एक्सओआर 0 तक पहुंच जाएंगी, इसलिए संचयक का अंतिम मूल्य उस संख्या के बराबर होगा जो तीन बार दिखाई देता है (यानी एक अतिरिक्त)।

Answer 2

तर्क यह है कि आपको केवल संचयक मूल्य को स्टोर करना होगा, और केवल एक बार सरणी के माध्यम से जाना होगा। वह बहुत चालाक है।

बेशक

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

बेशक यदि सरणी क्रमबद्ध करने के लिए क्रमबद्ध है, तो चीजें काफी आसान हैं। तो यह इस बात पर निर्भर करता है कि मूल्यों को सरणी में कैसे वितरित किया जाता है।

Answer 3

1 और 10,001 समावेशी के बीच प्रत्येक संख्या एक सरणी अनुक्रमणिका के रूप में दिखाई देती है। (सी एरे 0-अनुक्रमित नहीं हैं? अच्छा, इससे कोई फर्क नहीं पड़ता है, हम इस बात के अनुरूप हैं कि सरणी मान और सूचकांक दोनों 0 से शुरू होते हैं या दोनों 1 से शुरू होते हैं। मैं सरणी के साथ शुरू करूंगा 1, चूंकि यह सवाल कहता है।)

वैसे भी, हाँ, 1 और 10,001 समावेशी के बीच प्रत्येक संख्या, एक बार एक सरणी सूचकांक के रूप में दिखाई देती है। 1 और 10,000 समावेशी के बीच प्रत्येक संख्या एक बार सरणी मान के रूप में दिखाई देती है, डुप्लीकेट मान के अपवाद के साथ जो दो बार होता है। तो गणितीय रूप से, गणना हम समग्र रूप से कर रहे हैं:

1 xor 1 xor 2 xor 2 xor 3 xor 3 xor ... xor 10,000 xor 10,000 xor 10,001 xor D 

जहां डी डुप्लिकेट मान है। बेशक, गणना में शर्तें शायद उस क्रम में प्रकट नहीं होती हैं, लेकिन xor कम्यूटेटिव है, इसलिए हम शब्दों को फिर से व्यवस्थित कर सकते हैं। और n xor n प्रत्येक एन के लिए 0 है। तो उपर्युक्त

10,001 xor D 

इसे 10,001 के साथ xor और आपको डी, डुप्लिकेट मान मिलता है।

Answer 4

सवाल यह है: क्या आप असली दुनिया के लिए कम प्रासंगिकता के साथ चालाक लेकिन विशुद्ध रूप से अकादमिक xor चाल को कैसे जानना चाहते हैं, या आप इसे जानना चाहते हैं क्योंकि वास्तविक दुनिया में आप ऐसे प्रोग्राम लिख सकते हैं जो सरणी का उपयोग करते हैं? यह उत्तर बाद के मामले को संबोधित करता है।

नो-बकवास समाधान पूरे सरणी के माध्यम से जाना है और इसे जैसा सॉर्ट करना है। जब आप सॉर्ट करते हैं, तो सुनिश्चित करें कि कोई डुप्लिकेट मान नहीं हैं, यानी सार डेटा प्रकार "सेट" लागू करें। इसे आवंटित करने के लिए शायद दूसरी सरणी की आवश्यकता होगी और सॉर्टिंग समय लेने वाली होगी। चाहे चालाक xor चाल से अधिक या कम समय लेने वाला है, मुझे नहीं पता।

हालांकि, क्या अच्छा असली दुनिया में n आप के लिए अवर्गीकृत मूल्यों की एक सरणी है? अगर वे अपरिवर्तित हैं तो हमें यह मानना ​​होगा कि उनका आदेश किसी भी तरह महत्वपूर्ण है, इसलिए मूल सरणी को संरक्षित किया जाना चाहिए।यदि आप मूल सरणी के माध्यम से खोजना चाहते हैं या डुप्लिकेट, औसत मूल्य इत्यादि के लिए इसका विश्लेषण करना चाहते हैं तो आप वास्तव में इसका एक क्रमबद्ध संस्करण चाहते हैं। एक बार जब आप इसे हल कर लेंगे तो आप इसे "ओ लॉग एन" के साथ बाइनरी खोज सकते हैं।