डुप्लीकेट के बिना दो क्रमबद्ध पूर्णांक सरणी को कैसे छेड़छाड़ करें?

Question

यह एक साक्षात्कार प्रश्न है कि मैं प्रोग्रामिंग अभ्यास के रूप में उपयोग कर रहा हूं।

इनपुट: दो क्रमबद्ध पूर्णांक सरणियों एक और बढ़ते क्रम में और एन और एम क्रमश: विभिन्न आकार के बी

आउटपुट: एक आदेश है कि है कि दोनों में प्रदर्शित तत्व शामिल हैं बढ़ाने में हल कर पूर्णांक सरणी सी ए और बी

contraints: कोई डुप्लिकेट सी में अनुमति दी जाती है

उदाहरण: इनपुट के लिए ए = {3,6,8,9} और बी = {4,5,6,9,10,11}, आउटपुट सी = {6,9}

आपके उत्तरों के लिए धन्यवाद, सभी ! संक्षेप में, इस समस्या के दो मुख्य दृष्टिकोण हैं:

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

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

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

Answer 1

यह समस्या अनिवार्य रूप से एक में शामिल होने संचालन के लिए कम कर देता है और फिर एक फिल्टर आपरेशन (डुप्लिकेट को निकालने के लिए और केवल आंतरिक मैचों रखने के लिए)।

इनपुट दोनों पहले से ही क्रमबद्ध हैं, इसलिए इन्हें ओ (आकार (ए) + आकार (बी) के साथ merge join के माध्यम से कुशलता से हासिल किया जा सकता है।

फिल्टर आपरेशन हे (एन) होगा, क्योंकि में शामिल होने के उत्पादन में क्रमबद्ध हो जाता है और डुप्लिकेट तुम सब करने की है की जाँच करता है, तो प्रत्येक तत्व यह पहले से एक के रूप में ही है दूर करने के लिए। केवल आंतरिक मैचों को फ़िल्टर करना तुच्छ है, आप केवल उन तत्वों को त्यागें जो मेल नहीं खाते थे (बाहरी जुड़ते हैं)।

बेहतर प्रदर्शन प्राप्त करने के लिए समांतरता (शामिल होने और फ़िल्टर दोनों में) के अवसर हैं। उदाहरण के लिए हडोप पर Apache Pig ढांचा एक विलय में शामिल होने के parallel implementation प्रदान करता है।

प्रदर्शन और जटिलता (और इस प्रकार रखरखाव) के बीच स्पष्ट व्यापार-बंद हैं। तो मैं कहूंगा कि एक साक्षात्कार प्रश्न का एक अच्छा जवाब वास्तव में प्रदर्शन मांगों का ध्यान रखना होगा।

• सेट आधारित तुलना - ओ (nlogn) - अपेक्षाकृत धीमी, बहुत सरल, यदि कोई प्रदर्शन चिंता नहीं है तो इसका उपयोग करें। सरलता जीतता है।

• शामिल हों + फ़िल्टर - ओ (एन) - तेजी से, कोडिंग त्रुटि के लिए प्रवण, प्रदर्शन एक समस्या है। आदर्श रूप से ऐसा करने के लिए मौजूदा लाइब्रेरी का लाभ उठाने का प्रयास करें, या यदि उपयुक्त हो तो शायद डेटाबेस का भी उपयोग करें।

• समानांतर कार्यान्वयन - O (n/p) - बहुत तेजी से, जगह में अन्य बुनियादी सुविधाओं की आवश्यकता है, का उपयोग करता है, तो मात्रा बहुत बड़े और विकसित करने के लिए प्रत्याशित है और यह एक बड़ा प्रदर्शन टोंटी है।

(यह भी ध्यान रखें कि प्रश्न में समारोह intersectSortedArrays अनिवार्य रूप से एक संशोधित मर्ज में शामिल होने, जहां फिल्टर में शामिल होने के दौरान किया जाता है। आपके पास कोई प्रदर्शन नुकसान में बाद में फ़िल्टर कर सकते हैं, हालांकि एक स्मृति पदचिह्न थोड़ी वृद्धि हुई)।

अंतिम विचार।

वास्तव में, मुझे संदेह है कि अधिकांश आधुनिक वाणिज्यिक आरडीबीएमएस जुड़ने के उनके कार्यान्वयन में थ्रेड समांतरता प्रदान करते हैं, इसलिए हैडोप संस्करण प्रदान करता है मशीन-स्तर समांतरता (वितरण)। डिज़ाइन बिंदु दृश्य से, शायद प्रश्न का एक अच्छा, सरल समाधान डेटा को डाटाबेस पर रखना है, ए और बी पर सूचकांक (डेटा को प्रभावी ढंग से सॉर्ट करना) और SQL आंतरिक शामिल होने का उपयोग करना है।

Answer 2

कैसे के बारे में:

public static int[] intersectSortedArrays(int[] a, int[] b){ 
    int[] c = new int[Math.min(a.length, b.length)]; 
    int ai = 0, bi = 0, ci = 0; 
    while (ai < a.length && bi < b.length) { 
     if (a[ai] < b[bi]) { 
      ai++; 
     } else if (a[ai] > b[bi]) { 
      bi++; 
     } else { 
      if (ci == 0 || a[ai] != c[ci - 1]) { 
       c[ci++] = a[ai]; 
      } 
      ai++; bi++; 
     } 
    } 
    return Arrays.copyOfRange(c, 0, ci); 
} 

सैद्धांतिक रूप से यह मिलता-जुलता हो, लेकिन सरलीकरण के एक नंबर शामिल हैं।

मुझे नहीं लगता कि आप जटिलता पर सुधार कर सकते हैं।

संपादित करें: मैंने इस कोड को आजमाया है, और यह आपके सभी यूनिट परीक्षणों को पास करता है।

Answer 3

यदि आप 'इंटीजर' (ऑब्जेक्ट) सरणी का उपयोग कर रहे हैं और जावा एपीआई विधियों का उपयोग करना चाहते हैं, तो आप नीचे दिए गए कोड को देख सकते हैं। ध्यान दें कि उपरोक्त सूचीबद्ध अनुसार, नीचे दिए गए कोड में अधिक जटिलता है (क्योंकि यह एक डेटास्ट्रक्चर से कुछ रूपांतरण तर्क का उपयोग करता है) और स्मृति की खपत (ऑब्जेक्ट्स का उपयोग करने के कारण)।मैं सिर्फ यह कोशिश की (कहते):

public class MergeCollections { 
    public static void main(String[] args) { 
     Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
     Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13}; 

     Set<Integer> intSet1 = new TreeSet<Integer>(); 
     intSet1.addAll(Arrays.asList(intArray1)); 
     intSet1.addAll(Arrays.asList(intArray2)); 
     System.out.println(intSet1); 
    } 
} 

और उत्पादन:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13] 

इसके अलावा, इस लिंक की जाँच करें: Algolist - Algo to merge sorted arrays

संपादित: बदली गई HashSet TreeSet को

संपादित करें 2: अब प्रश्न संपादित किया जाता है और स्पष्ट है, मैं एक सरल उपाय जोड़ रहा चौराहे खोजने के लिए कि:

public class Intersection { 
    public static void main(String[] args) { 
     Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
     Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13}; 

     List<Integer> list1 = Arrays.asList(intArray1); 
     Set<Integer> commonSet = new TreeSet<Integer>(); 
     for(Integer i: intArray2) { 
      if(list1.contains(i)) { 
       commonSet.add(i); 
      } 
     } 

     System.out.println(commonSet); 
    } 
} 

Answer 4

अगर यह इस तरह से समस्या का समाधान करने के लिए एक अच्छा विचार है मैं नहीं जानता:

कहना

A,B are 1 based arrays 
    A.length=m 
    B.length=n 

1), एक सरणी, सी init मिनट (एम, एन) लंबाई

2) के साथ ही पहली और आखिरी तत्व की जाँच करके आम हिस्सा पर ध्यान केंद्रित। यहां बाइनरी खोज का उपयोग किया जा सकता है। कुछ शब्दों को बचाने के लिए एक उदाहरण लेते हैं:

A[11,13,15,18,20,28,29,80,90,100.........300,400] 
    ^          ^
B[3,4,5,6,7.8.9.10.12,14,16,18,20,..400.....9999] 
        ^   ^


then we need only focus on 

    A[start=1](11)-A[end=m](400) 
    and 
    B[start=9](12)-B[end](400) 

3)। दोनों Arrays के रेंज(end-start) की तुलना करें। छोटे रेंज के साथ सरणी ले, कहना ए, A[start] ~ A[end] से प्रत्येक तत्व A[i] के लिए, द्विआधारी खोज B[start,end] में B.start foundIdx + 1,

लिए करते हैं,

• अगर पाया, सी में तत्व डाल दिया, रीसेट

• अन्यथा B.start सबसे छोटा तत्व [जे], जो बी [जे] एक [मैं], सीमा की अवधि कम करने के लिए

4) सह से अधिक है पर सेट है ntinue 3) ए [प्रारंभ, अंत] में सभी तत्वों को संसाधित नहीं किया गया था।

• चरण 1 द्वारा, यदि दो ऐरे के बीच कोई अंतर नहीं है तो हम मामले को पा सकते हैं।
• चरण 3 में बाइनरी खोज करते समय, हम ए [i] ए [i-1] की तुलना करते हैं, यदि समान है, तो ए [i] छोड़ें। सी में तत्व रखने के लिए अद्वितीय हैं।

इस तरह से, खराब मामला एलजी (एन!) होगा यदि (ए और बी समान हैं)? निश्चित नहीं।

औसत मामले?

Answer 5

यहाँ एक स्मृति सुधार है:

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

संपादित करें: एक और चीज जो मैं बदलूंगा, और यह थोड़ा सा नाइट-पिक्य हो सकता है, यह है कि मैं अनबाउंड लूप का उपयोग करने से बचूंगा जब पुनरावृत्ति की सबसे बुरी स्थिति संख्या हाथ से पहले जानी जाती है।

Answer 6

परिणाम संग्रहीत करने के लिए सरणीसूची का उपयोग करना।

public ArrayList<Integer> arrayIntersection(int [] a, int[] b) 
{ 
    int len_a=a.length; 
    int len_b=b.length; 
    int i=0; 
    int j=0; 
    ArrayList<Integer> alist=new ArrayList(); 

    while(i<len_a && j<len_b) 
    { 
     if(a[i]<b[j]) 
      i++; 
     else if(a[i]>b[j]) 
      j++; 
     else if(a[i]==b[j]) 
     { 
      alist.add(a[i]); 
      i++; 
      j++; 

     } 
    } 

    return alist;  
    }