दो क्रमबद्ध सरणी का चौराहे

Question

दो क्रमबद्ध सरणी दिए गए: A और B। सरणी A का आकार La है और सरणी B का आकार Lb है। A और B के चौराहे को कैसे ढूंढें?

यदि LaLb से बहुत बड़ा है, तो क्या अंतरंग खोज एल्गोरिदम के लिए कोई अंतर होगा?

Answer 1

set_intersectionhere के रूप में उपयोग करें। सामान्य कार्यान्वयन मर्ज-सॉर्ट एल्गोरिदम के विलय भाग के समान काम करेगा।

Answer 2

चूंकि यह एक HW तरह लग रहा है ... मैं तुम्हें एल्गोरिथ्म देंगे:

Let arr1,arr2 be the two sorted arrays of length La and Lb. 
Let i be index into the array arr1. 
Let j be index into the array arr2. 
Initialize i and j to 0. 

while(i < La and j < Lb) do 

    if(arr1[i] == arr2[j]) { // found a common element. 
     print arr[i] // print it. 
     increment i // move on. 
     increment j 
    } 
    else if(arr1[i] > arr2[j]) 
     increment j // don't change i, move j. 
    else 
     increment i // don't change j, move i. 
end while 

Answer 3

void Intersect() 
{ 
    int la, lb; 
    la = 5; 
    lb = 100; 
    int A[5]; 
    int i, j, k; 
    i = j = k = 0; 
    for (; i < 5; ++i) 
     A[i] = i + 1; 
    int B[100]; 
    for (; j < 100; ++j) 
     B[j] = j + 2; 
    int newSize = la < lb ? la : lb; 
    int* C = new int[newSize]; 
    i = j = 0; 
    for (; k < lb && i < la && j < lb; ++k) 
    { 
     if (A[i] < B[j]) 
      i++; 
     else if (A[i] > B[j]) 
      j++; 
     else 
     { 
      C[k] = A[i]; 
      i++; 
      j++; 
     } 
    } 
    for (k = 0; k < newSize; ++k) 
     cout << C[k] << NEWLINE; 
} 

Answer 4

मैं अब थोड़ी देर के लिए एक ही समस्या के साथ संघर्ष कर रहा है, अब तक मैं के साथ आया था:

1. रैखिक मिलान जो ओ (एम + एन) को सबसे खराब मामले में उत्पन्न करेगा। आप मूल रूप से दो बिंदुओं (ए और बी) को प्रत्येक सरणी की शुरुआत के लिए इंगित करते हैं। फिर अग्रिम सूचक जो छोटे मान को इंगित करता है, जब तक कि आप किसी एक सरणी के अंत तक नहीं पहुंच जाते, जो कोई छेड़छाड़ नहीं करेगा। यदि किसी भी समय आपके पास * ए == * बी है - यहां आपका चौराहे आता है।

2. बाइनरी मिलान। जो सबसे खराब मामले में ~ ओ (एन * लॉग (एम)) पैदा करता है। आप मूल रूप से छोटे सरणी को चुनते हैं और छोटे सरणी के सभी तत्वों की बड़ी सरणी में बाइनरी खोज करते हैं। यदि आप अधिक फैंसी बनना चाहते हैं, तो आप अंतिम स्थिति का भी उपयोग कर सकते हैं जहां बाइनरी खोज विफल रही और इसे अगले बाइनरी खोज के लिए शुरुआती बिंदु के रूप में उपयोग करें। इस तरह आप सबसे खराब मामले में मामूली सुधार करते हैं लेकिन कुछ सेटों के लिए यह चमत्कार कर सकता है :)

3. डबल बाइनरी मिलान। यह नियमित बाइनरी मिलान की एक भिन्नता है। असल में आप छोटे सरणी के बीच से तत्व प्राप्त करते हैं और बड़े सरणी में बाइनरी खोज करते हैं। यदि आपको कुछ भी नहीं मिलता है तो आप आधे में छोटे सरणी काटते हैं (और हाँ आप पहले से इस्तेमाल किए गए तत्व को टॉस कर सकते हैं) और आधे में बड़ी सरणी काट लें (बाइनरी सर्च विफलता बिंदु का उपयोग करें)। और फिर प्रत्येक जोड़ी के लिए दोहराना। परिणाम ओ (एन * लॉग (एम) से बेहतर हैं) लेकिन मैं उनकी गणना करने के लिए बहुत आलसी हूं।

ये दो सबसे बुनियादी हैं। दोनों में योग्यता है। रैखिक लागू करने के लिए थोड़ा आसान है। बाइनरी एक तर्कसंगत रूप से तेज़ है (हालांकि वहां कई मामले हैं जब रैखिक मिलान बाइनरी से बेहतर होगा)।

यदि कोई इससे बेहतर कुछ जानता है तो मुझे यह सुनना अच्छा लगेगा। मिलान करने वाले सरणी मैं इन दिनों क्या करता हूं।

पीएस मुझे "रैखिक मिलान" और "बाइनरी मिलान" शब्दों पर उद्धरण न दें क्योंकि मैंने उन्हें स्वयं बनाया है और शायद इसके लिए पहले से ही फैंसी नाम है।

Answer 5

//intersection of two arrays 
#include<iostream> 
using namespace std; 
int main() { 

int i=0,j=0,m,n; 
int arr1[i],arr2[j]; 
cout<<"Enter the number of elements in array 1: "; 
cin>> m; 
cout<<"Enter the number of elements in array 2: "; 
cin>>n; 
for (i=0;i<m;i++){ 
    cin>> arr1[i]; 
} 
for(j=0;j<n;j++){ 
    cin>> arr2[j]; 
} 
for(j=0;j<n;j++){ 
    for(i=0;i<m;i++) { 
     if (arr1[i] == arr2[j]){ 
     cout<< arr1[i]; 
     cout << ' '; 
     break; 
     } 
    } 
}  

return 0; 
} 

Answer 6

के दो हल कर सरणियों पर विचार करें: -

int[] array1 = {1,2,3,4,5,6,7,8}; 
int[] array2 = {2,4,8}; 

int i=0, j=0; //taken two pointers 

पाश तक दोनों संकेत संबंधित लंबाई तक पहुंच चलेंगे है।

while(i<array1.length || j<array2.length){ 
    if(array1[i] > array2[j])  //if first array element is bigger then increment 2nd pointer 
     j++; 
    else if(array1[i] < array2[j]) // same checking for second array element 
     i++; 
    else {       //if both are equal then print them and increment both pointers 
     System.out.print(a1[i]+ " "); 

     if(i==a1.length-1 ||j==a2.length-1) //one additional check for ArrayOutOfBoundsException 
      break; 
     else{ 
      i++; 
      j++; 
     } 
    } 
}   

आउटपुट हो जाएगा: -

2 4 8