2 हल कर सरणियों

Question

में आम तत्वों का पता लगाएं

संभव डुप्लिकेट:
The intersection of two sorted arrays

हम दो क्रमबद्ध सरणियों ए और बी, के अलावा अन्य सरणी, में सभी तत्वों के साथ एक तुलना कैसे करने के लिए है अपने सामान्य तत्वों के साथ सरणी को खोजने के लिए एक सर्वोत्तम एल्गोरिदम तैयार करें?

Answer 1

दो संकेत पकड़ो: प्रत्येक सरणी के लिए एक।

i <- 0, j <- 0 
repeat while i < length(arr1) and j < length(arr2): 
    if arr1[i] > arr2[j]: increase j 
    else if arr1[i] < arr2[j]: increase i 
    else : output arr[i], increase both pointers 

विचार है, अगर डेटा, सॉर्ट हो जाता है, तो तत्व "बहुत बड़ा" एक सरणी में है, यह हो जाएगा अन्य सभी सरणी में छोड़ दिया तत्वों के लिए "बहुत बड़ा" - के बाद से यह सॉर्ट की गई है।

यह समाधान डेटा पर एक ही ट्रेवर्सल की आवश्यकता है। O(n) (अच्छे स्थिरांक के साथ)।

Answer 2

के अलावा अन्य सरणी में सभी तत्वों के साथ एक तुलना

आप एक [] [] बी को तुलना करना होगा आदेश को पता है कि वे एक ही हैं - जब तक आप एक बहुत जानते हैं वे किस प्रकार के डेटा को पकड़ सकते हैं। तुलना की प्रकृति में शायद कई समाधान हैं और आवश्यकतानुसार अनुकूलित किया जा सकता है।

यदि सरणी बहुत सख्ती से बनाई गई हैं यानी ज्ञात पैटर्न के अनुक्रमिक मान हैं और हमेशा एक ज्ञात बिंदु से शुरू होते हैं तो आप केवल प्रत्येक सरणी की लंबाई को देख सकते हैं और जान सकते हैं कि सभी आइटम आम हैं या नहीं।

यह दुर्भाग्य से एक बहुत यथार्थवादी या उपयोगी सरणी की तरह ध्वनि नहीं है और इसलिए आप के लिए जाँच करने के लिए वापस आ रहे हैं एक [i] में बी []

Answer 3

तो दो सरणियों (जैसे कि, AN तत्व है की लंबाई और BM तत्व) है समान हैं, तो सबसे अच्छा तरीका रैखिक एक की खोज एक और सरणी में सरणी के तत्वों प्रदर्शन करने के लिए किया जाएगा। बेशक, चूंकि सरणी को क्रमबद्ध किया जाता है, अगली खोज शुरू होनी चाहिए जहां पिछली खोज बंद हो गई है। यह "क्रमबद्ध सरणी विलय" एल्गोरिदम में उपयोग किया जाने वाला क्लासिक सिद्धांत है। O(N + M) पर जटिलता।

लंबाई काफी अलग (जैसे कि, M << N), तो एक और अधिक इष्टतम दृष्टिकोण छोटे सरणी के तत्वों के माध्यम से पुनरावृति और लंबे समय तक सरणी में इन मूल्यों को देखने के लिए द्विआधारी खोज का उपयोग किया जाएगा रहे हैं। उस मामले में जटिलता O(M * log N) है।

आप O(M * log N) देख सकते हैं की तुलना में बेहतर O(N + M) अगर M बहुत खराब अन्यथा N की तुलना में छोटे, और है।

सरणी आकार में अंतर जो एक से दूसरे दृष्टिकोण से स्विच उत्प्रेरित करने चाहिए कुछ व्यावहारिक दृष्टिकोण पर निर्भर करता है। यदि आपके डेटा के साथ व्यावहारिक प्रयोगों के आधार पर चुना जाना चाहिए।

इन दो दृष्टिकोण (रेखीय और द्विआधारी खोज) एक एकल एल्गोरिथ्म में "मिश्रित" हो सकता है। आइए M <= N मान लें। उस स्थिति में चलिए चरण मान S = [N/M] चुनें।आप सरणी A से पहले तत्व लेते हैं और स्ट्रैड चरण B में उस तत्व के लिए रैखिक खोज चरण S के साथ करते हैं, जिसका अर्थ है कि आप B[0], B[S], B[2*S], B[3*S], ... तत्वों को जांचते हैं। एक बार जब आप इंडेक्स रेंज [S*i, S*(i+1)] पाते हैं जिसमें संभावित रूप से वह तत्व शामिल होता है जिसे आप खोज रहे हैं, तो आप बाइनरी पर जाएं B के उस सेगमेंट के अंदर खोज करें। किया हुआ। A के अगले तत्व के लिए स्ट्रैडल रैखिक खोज शुरू होती है जहां पिछली खोज छोड़ी गई थी। (एक साइड नोट के रूप में, यह S के मूल्य को 2 की शक्ति के बराबर चुनने का अर्थ हो सकता है)।

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