घटनाओं की संख्या के साथ संख्या

Question

एक सरणी को देखते हुए जहां प्रत्येक संख्या की घटनाओं की संख्या एक संख्या को छोड़कर अजीब है, जिनकी संख्याओं की संख्या भी है। घटनाओं के साथ संख्या भी खोजें।

उदा

1, 1, 2, 3, 1, 2, 5, 3, 3 

आउटपुट होना चाहिए:

2 

नीचे की कमी कर रहे हैं:

1. नंबर रेंज में नहीं हैं।
2. इसे जगह में करें।
3. आवश्यक समय जटिलता ओ (एन) है।
4. ऐरे में नकारात्मक संख्याएं हो सकती हैं।
5. ऐरे सॉर्ट नहीं किया गया है।

ऊपर की कमी के साथ, मेरे सारे विचार विफल रहा है: तुलना आधारित छंटाई, गिनती तरह, BST की, हैशिंग, जानवर बल।

मुझे जानकर उत्सुकता है: क्या XORING यहां काम करेगा? यदि हां, तो कैसे?

Answer 1

निम्नलिखित आलेख देखें: Sorting algorithm that runs in time O(n) and also sorts in place, यह मानते हुए कि अंकों की अधिकतम संख्या निरंतर है, हम ओ (एन) समय में सरणी को जगह में सॉर्ट कर सकते हैं।

उसके बाद यह प्रत्येक संख्या की उपस्थिति को गिनने का मामला है, जो एक संख्या को खोजने के लिए औसत एन/2 समय लेगा, जिसकी संख्याओं की संख्या भी है।

Answer 2

यह समस्या कई दिनों से मेरी मेट्रो सवारी पर कब्जा कर रही है। मेरे विचार यहाँ हैं।

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

दो चरम subproblems जो मन में आ निम्नलिखित हैं:

• सरणी दो मानों शामिल हैं: उनमें से एक समान बार दोहराया है, और अन्य विषम संख्या में दोहराया है बार।
• सरणी में एन -1 अलग-अलग मान हैं: सभी मान एक बार मौजूद हैं, एक मूल्य को छोड़कर दो बार मौजूद हैं।

शायद हमें विभिन्न मूल्यों की संख्या की जटिलता से मामलों को विभाजित करना चाहिए।

अगर हम मान लें कि विभिन्न मूल्यों की संख्या हे (1) है, प्रत्येक सरणी mn से स्वतंत्र साथ m अलग-अलग मान, होगा। इस मामले में, हम मूल सरणी को मिटाने और प्रत्येक मान की घटनाओं की गिनती के माध्यम से लूप कर सकते हैं।उदाहरण में यह

1, 1, 2, 3, 1, 2, 5, 3, 3 -> First value is 1 so count and erase all 1 
2, 3, 2, 5, 3, 3 -> Second value is 2, count and erase 
-> Stop because 2 was found an even number of times. 

यह O(mn) की एक जटिलता है, जो O(n) करने का मूल्यांकन करती है पहले चरम उदाहरण का समाधान होगा देना होगा।

बेहतर है: यदि विभिन्न मानों की संख्या O(1) है, तो हम हैश मानचित्र के अंदर मूल्य उपस्थिति की गणना कर सकते हैं, पूरे सरणी को पढ़ने के बाद उनके माध्यम से जा सकते हैं और एक बार कई बार दिखाई देते हैं। यह चौड़ा अभी भी O(1) मेमोरी माना जाएगा।

दूसरा चरम मामला एक सरणी के अंदर केवल दोहराया गया मूल्य ढूंढने में शामिल होगा। O(n) में यह असंभव प्रतीत होता है, लेकिन ऐसे विशेष मामले हैं जहां हम कर सकते हैं: यदि सरणी में n तत्व और मूल्य {1, n-1} + दोहराए गए मान (या जैसे कुछ संस्करण x और y के बीच सभी संख्याएं हैं)। इस मामले में, हम योग सभी मान, योग से n(n-1)/2 घटाएं, और दोहराए गए मूल्य को पुनः प्राप्त करें।

सरणी, या सामान्य मामले में जहां mn पर स्थिर नहीं है, निरंतर स्मृति में और O(n) समय मेरे लिए असंभव लगता है अंदर यादृच्छिक मूल्यों के साथ दूसरे चरम मामले को सुलझाने।

अतिरिक्त नोट: यहां, XORING काम नहीं करता है क्योंकि हम जिस नंबर को चाहते हैं वह कई बार प्रकट होता है और अन्य कई बार प्रकट होते हैं। यदि समस्या थी "विषम कई बार दिखाई देने वाली संख्या दें, तो अन्य सभी संख्या भी कई बार दिखाई देती है" हम सभी मूल्यों को एक्सओआर कर सकते हैं और अंत में अजीब को ढूंढ सकते हैं।

हम एक विधि इस तर्क का उपयोग कर देखने के लिए कोशिश कर सकते: हम एक समारोह, कि एक नंबर पर कई बार विषम संख्या में लागू किया की तरह कुछ की जरूरत 0 उपज होगा, और समय की सम संख्या पहचान होगा। ऐसा मत सोचो यह संभव है।

Answer 3

परिचय

यहाँ एक संभव समाधान है। यह बल्कि विकसित है और व्यावहारिक नहीं है, लेकिन फिर भी समस्या है। अगर मेरे विश्लेषण में छेद है तो मैं किसी भी टिप्पणी की सराहना करता हूं। अगर यह एक "आधिकारिक" समाधान के साथ होमवर्क या चुनौती समस्या थी, तो मुझे यह भी देखना अच्छा लगेगा कि मूल पोस्टर अभी भी इसके बारे में है, क्योंकि यह पूछे जाने के बाद एक महीने से अधिक समय बीत चुका है।

सबसे पहले, हमें समस्या के कुछ अस्पष्ट विवरणों को दूर करने की आवश्यकता है। समय जटिलता O(N) है, लेकिन N क्या है? अधिकांश टिप्पणीकार मानते हैं कि N सरणी में तत्वों की संख्या है। यह ठीक होगा अगर सरणी में संख्याएं अधिकतम आकार के निश्चित थीं, इस मामले में माइकल जी का रेडिक्स सॉर्ट का समाधान समस्या को हल करेगा। लेकिन, मैं मूल पोस्टर द्वारा स्पष्टीकरण की अनुपस्थिति में बाधा # 1 की व्याख्या करता हूं, क्योंकि कहता है कि अंकों की अधिकतम संख्या तय नहीं की जानी चाहिए। इसलिए, यदि n (लोअरकेस) सरणी में तत्वों की संख्या है, और औसत तत्वों की लंबाई है, तो कुल इनपुट आकार mn के साथ संघर्ष करने के लिए है। समाधान समय पर कम बाध्य O(mn) है क्योंकि यह समाधान को सत्यापित करने के लिए आवश्यक इनपुट का रीड-थ्रू टाइम है। इसलिए, हम एक समाधान चाहते हैं जो कुल इनपुट आकार N = nm के संबंध में रैखिक है।

उदाहरण के लिए, हम n = m हो सकता है, कि sqrt(N) औसत लंबाई के sqrt(N) तत्वों है। तुलनात्मक प्रकार O(log(N) sqrt(N)) < O(N) संचालन लेगा, लेकिन यह एक जीत नहीं है, क्योंकि ऑपरेशन औसत पर O(m) = O(sqrt(N)) समय लेते हैं, इसलिए हम O(N log(N)) पर वापस आ गए हैं।

इसके अलावा, एक मूलांक तरह O(mn) = O(N) ले mऔसत लंबाई के बजाय अधिकतम लंबाई होने पर होता। अधिकतम और औसत लंबाई उसी क्रम पर होगी यदि संख्याओं को कुछ सीमाबद्ध सीमा में गिरने के लिए माना जाता था, लेकिन यदि नहीं, तो हमारे पास अंकों की एक बड़ी और परिवर्तनीय संख्या के साथ एक छोटा प्रतिशत हो सकता है और अंकों की एक छोटी संख्या के साथ एक बड़ा प्रतिशत हो सकता है । उदाहरण के लिए, संख्याओं का 10% लंबाई m^1.1 और 90% लंबाई m*(1-10%*m^0.1)/90% हो सकता है। औसत लंबाई m होगी, लेकिन अधिकतम लंबाई m^1.1 है, इसलिए रेडिक्स सॉर्ट O(m^1.1 n) > O(N) होगा।

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

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

संभव समाधान

पहले, बाधा वहाँ नकारात्मक संख्या हो सकता है कि एक खाली एक है। डेटा के माध्यम से एक पास के साथ, हम न्यूनतम तत्व, z, और तत्वों की संख्या, n रिकॉर्ड करेंगे। दूसरे पास पर, हम प्रत्येक तत्व में (3-z) जोड़ देंगे, इसलिए सबसे छोटा तत्व अब 3 है। (ध्यान दें कि परिणामों की निरंतर संख्या परिणामस्वरूप बहती जा सकती है, इसलिए हमें पहले डेटा के माध्यम से अतिरिक्त पास की निरंतर संख्या करना चाहिए इन समाधानों के लिए परीक्षण करें।) एक बार हमारे पास समाधान होने के बाद, हम इसे अपने मूल रूप में वापस करने के लिए (3-z) घटाते हैं। अब हमारे पास तीन विशेष मार्कर मान 0, 1, और 2 उपलब्ध हैं, जो स्वयं तत्व नहीं हैं।

चरण 1

median-of-medians selection algorithm का उपयोग 90 प्रतिशत तत्व, p निर्धारित करने के लिए, सरणी A की और सेट दो सेट S और T में सरणी विभाजन जहां Sp और T से अधिक 10% of n तत्व है p से कम तत्व हैं। यह O(n) चरणों (O(N) कुल) के औसत पर O(m) ले जाने के चरणों के साथ लेता है। p से मिलान करने वाले तत्वों को या तो S या T में रखा जा सकता है, लेकिन सादगी के लिए, एक बार सरणी के माध्यम से चलाएं और p का परीक्षण करें और 0 के साथ इसे बदलकर इसे खत्म करें।S मूल रूप से इंडेक्स 0..s स्पैन करता है, जहां sn है, और T सेट करें शेष 90% इंडेक्स s+1..n पर फैलाएं।

चरण 2

अब हम i in 0..s लूप करने के लिए जा रहे हैं और प्रत्येक तत्व e_i के लिए हम s+1..n में एक हैश समारोह h(e_i) गणना करने के लिए जा रहे हैं। समान वितरण प्राप्त करने के लिए हम universal hashing का उपयोग करेंगे। तो, हमारे हैशिंग फ़ंक्शन गुणा और जोड़ करेंगे और इसकी लंबाई के संबंध में प्रत्येक तत्व पर रैखिक समय लेंगे।

हम टकराव के लिए एक संशोधित रैखिक जांच कर रणनीति का उपयोग करेंगे:

1. h(e_i)T के एक सदस्य के कब्जे में है (A[ h(e_i) ] < p अर्थ लेकिन एक मार्कर 1 या 2 नहीं है) या 0 है। यह एक हैश टेबल मिस है। स्लॉट i और h(e_i) से तत्वों को स्वैप करके e_i डालें।

2. h(e_i)S (जिसका अर्थ है A[ h(e_i) ] > p) के एक सदस्य या मार्कर 1 या 2 के कब्जे में है। यह एक हैश टेबल टकराव है। e_i या T या 0 के सदस्य का डुप्लिकेट होने तक रैखिक जांच करें।

   • T के एक सदस्य है, यह एक फिर से एक हैश तालिका याद आती है, तो i स्लॉट को स्वैप करके e_i(1.) में के रूप में सम्मिलित करें।

   • यदि e_i का डुप्लिकेट है, तो यह हैश तालिका हिट है। अगले तत्व की जांच करें। यदि वह तत्व 1 या 2 है, तो हमने e_i को पहले से कहीं अधिक देखा है, 1 एस 2 एस में बदलें और इसके विपरीत समानता में इसके परिवर्तन को ट्रैक करने के लिए। यदि अगला तत्व 1 या 2 नहीं है, तो हमने केवल एक बार पहले e_i देखा है। हम को अब भी कई बार देख चुके हैं, यह इंगित करने के लिए हम 2 को अगले तत्व में संग्रहीत करना चाहते हैं। हम अगले "खाली" स्लॉट के लिए देखो, कि एक T के एक सदस्य है जो हम स्लॉट i, या एक 0 में चले जाएंगे, और तत्वों वापस शिफ्ट सूचकांक h(e_i)+1 नीचे से ऊपर तो हम करने के लिए h(e_i) के बगल में कमरा है के कब्जे में है हमारी समानता जानकारी स्टोर करें। ध्यान दें कि हमें e_i को फिर से स्टोर करने की आवश्यकता नहीं है, इसलिए हमने कोई अतिरिक्त स्थान नहीं उपयोग किया है।

तो बुनियादी तौर पर हम साथ एक कार्यात्मक हैश तालिका है 9 गुना तत्वों हम हैश करने के लिए इच्छा के रूप में स्लॉट की संख्या। एक बार जब हम हिट प्राप्त करना शुरू कर देते हैं, तो हम समानता की जानकारी भी संग्रहित करना शुरू करते हैं, इसलिए हम केवल 4.5 गुना संख्या स्लॉट के साथ समाप्त हो सकते हैं, फिर भी बहुत कम लोड फैक्टर। ऐसी कई टकराव रणनीतियों हैं जो यहां काम कर सकती हैं, लेकिन चूंकि हमारा लोड कारक कम है, इसलिए टकराव की औसत संख्या भी कम होनी चाहिए और रैखिक जांच उन्हें औसतन उपयुक्त समय जटिलता के साथ हल करनी चाहिए।

चरण 3

एक बार जब हम s+1..n में 0..s के तत्वों hashing समाप्त हो गया है, हम s+1..n बढ़ावा देते हैं। अगर हमें 2 के बाद एस का तत्व मिलता है, तो यह हमारा लक्ष्य तत्व है और हम कर रहे हैं। के e के बाद कोई भी तत्व S का एक और तत्व इंगित करता है e केवल एक बार सामना किया गया था और इसे शून्य किया जा सकता है। इसी तरह e के बाद 1 का अर्थ है कि हमने e को कई बार देखा, और हम e और मार्कर 1 को शून्य कर सकते हैं।

रिंस और के रूप में वांछित

हम अपने लक्ष्य तत्व नहीं मिला है, तो हम प्रक्रिया को दोहराने दोहराएँ। हमारा 90 वां प्रतिशत विभाजन nA की शुरुआत में शेष सबसे बड़े तत्वों को छोड़ देगा और शेष 0 -मार्कर स्लॉट समेत शेष तत्वों को अंत में ले जाएगा। हम पहले से ही हैशिंग के साथ जारी है। हमें इसे हर बार 10 बार करना है क्योंकि हम हर बार n का 10% संसाधित करते हैं।

मंझला के- माध्यिकाओं एल्गोरिथ्म के माध्यम से समापन विश्लेषण

विभाजन O(N) के समय जटिलता है, जो हम 10 बार, अभी भी O(N) करना है। हैश टेबल लोड कम होने के बाद प्रत्येक हैश ऑपरेशन O(1) लेता है और हैश ऑपरेशंस कुल प्रदर्शन (10 पुनरावृत्ति में से प्रत्येक के लिए लगभग 10% एन) किया जाता है। n तत्वों में से प्रत्येक के लिए उनके पास गणना की गई हैश फ़ंक्शन है, समय की जटिलता उनकी लंबाई के लिए रैखिक है, इसलिए O(m) सभी तत्वों पर औसत पर। इस प्रकार, कुल मिलाकर हैशिंग ऑपरेशन O(mn) = O(N) हैं। इसलिए, अगर मैंने इसका सही ढंग से विश्लेषण किया है, तो पूरे पर इस एल्गोरिदम O(N)+O(N)=O(N) है। (यह O(n) भी है यदि अतिरिक्त, गुणा, तुलना, और स्वैपिंग के संचालन इनपुट के संबंध में निरंतर समय माना जाता है।)

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