एल्गोरिदम यह बताने के लिए कि क्या दो सरणी के समान सदस्य हैं

Question

दो एरे की तुलना करने के लिए सबसे अच्छा एल्गोरिदम क्या है यह देखने के लिए कि उनके पास एक ही सदस्य हैं या नहीं?

मान लें कि कोई डुप्लिकेट नहीं है, सदस्य किसी भी क्रम में हो सकते हैं, और न तो हल किया जा सकता है।

compare(
    [a, b, c, d], 
    [b, a, d, c] 
) ==> true 

compare(
    [a, b, e], 
    [a, b, c] 
) ==> false 

compare(
    [a, b, c], 
    [a, b] 
) ==> false 

Answer 1

स्पष्ट जवाब होगा:

1. क्रमबद्ध दोनों सूचियों, तो प्रत्येक तत्व की जांच देखने के लिए कि वे समान
2. के माध्यम से एक hashtable करने के लिए एक सरणी से आइटम जोड़ें, तो पुनरावृति कर रहे हैं अन्य सरणी, जाँच प्रत्येक आइटम हैश में है कि
3. nickf की पुनरावृत्ति खोज एल्गोरिथ्म

आप जो भी इस्तेमाल करेंगे, उस पर निर्भर करेगा कि आप पहले सूचियों को सॉर्ट कर सकते हैं या नहीं, और आपके पास एक अच्छा हैश एल्गोरिदम आसान है या नहीं।

Answer 2

सबसे अच्छा मैं सोच सकता हूं ओ (एन^2), मुझे लगता है।

function compare($foo, $bar) { 
    if (count($foo) != count($bar)) return false; 

    foreach ($foo as $f) { 
     foreach ($bar as $b) { 
      if ($f == $b) { 
       // $f exists in $bar, skip to the next $foo 
       continue 2; 
      } 
     } 
     return false; 
    } 
    return true; 
} 

Answer 3

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

डुप्लिकेट की उपस्थिति में यह काम करने के लिए, ट्रैक करें कि प्रत्येक तत्व में से कितने देखा गया है। पहली सरणी पर लूपिंग करते समय वृद्धि, और दूसरी सरणी पर लूपिंग करते समय कमी। दूसरी सरणी पर लूप के दौरान, यदि आपको हैश तालिका में कुछ नहीं मिल रहा है, या यदि काउंटर पहले से शून्य पर है, तो वे असमान हैं। कुल गणना की तुलना करें।

डुप्लिकेट की उपस्थिति में काम करने वाली एक और विधि दोनों सरणी को क्रमबद्ध करने और रैखिक तुलना करने के लिए है। यह ओ (एन * लॉग (एन) होना चाहिए)।

Answer 4

मैं पहले एक तरह का उपयोग करने और पहले दोनों को क्रमबद्ध करने का सुझाव दूंगा। फिर आप प्रत्येक सरणी के पहले तत्व की तुलना दूसरी और फिर की तुलना करेंगे।

यदि आपको कोई मेल नहीं मिला तो आप रुक सकते हैं।

Answer 5

यदि आप पहले दोनों सरणी सॉर्ट करते हैं, तो आपको ओ (एन लॉग (एन)) मिल जाएगा।

Answer 6

शायद हैशैप्स का उपयोग करने का सबसे अच्छा तरीका है। चूंकि हैशपैप में सम्मिलन ओ (1) है, इसलिए एक सरणी से हैशमैप बनाना ओ (एन) लेना चाहिए। फिर आपके पास एन लुकअप हैं, जिनमें से प्रत्येक ओ (1) लेता है, इसलिए एक और ओ (एन) ऑपरेशन। सब कुछ, यह ओ (एन) है।

अजगर में:

def comparray(a, b): 
    sa = set(a) 
    return len(sa)==len(b) and all(el in sa for el in b) 

Answer 7

तरीके सी # में ऐसा करने में बनाया अनदेखी, आप कुछ इस तरह कर सकता है:

इसकी हे (1) सबसे अच्छा मामले में, हे (एन) (प्रति सूची) सबसे खराब मामले में।

public bool MatchArrays(object[] array1, object[] array2) 
{ 
    if (array1.length != array2.length) 
     return false; 

    bool retValue = true; 

    HashTable ht = new HashTable(); 

    for (int i = 0; i < array1.length; i++) 
    { 
     ht.Add(array1[i]); 
    } 

    for (int i = 0; i < array2.length; i++) 
    { 
     if (ht.Contains(array2[i]) 
     { 
     retValue = false; 
     break; 
     } 
    } 

    return retValue; 
} 

Answer 8

मान लिया जाये कि आप मूल सरणियों परेशान करने के लिए नहीं करना चाहते हैं और अंतरिक्ष एक विचार, दोनों सरणियों छँटाई की तुलना में कम स्थान का उपयोग करता है कि एक और ओ (n.log (एन)) समाधान है:

अवास्तविक लौटाते
1. अगर सरणियों आकार में पहली सरणी अलग
2. क्रमबद्ध - ओ (n.log (एन)) समय, अतिरिक्त आवश्यक स्थान एक सरणी
3. का आकार 2 सरणी में प्रत्येक तत्व के लिए, यदि जाँच है यह की क्रमबद्ध प्रतिलिपि में है जो बाइनरी खोज का उपयोग करके पहली सरणी है - ओ (एन.एलएल (एन)) समय

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

[जोड़ा शब्दकोश/सेट/हैश लुकअप सुझाव समाधान समीक्षा करने के बाद:]

व्यवहार में मैं एक हैश का उपयोग करेंगे। कई लोगों ने हे (1) हैंश के लिए व्यवहार किया है, जिससे उन्हें एक हैश-आधारित समाधान निष्कर्ष निकाला जा रहा है ओ (एन)। विशिष्ट आवेषण/लुकअप ओ (1) के करीब हो सकते हैं, और कुछ हैशिंग योजनाएं सबसे बुरी स्थिति ओ (1) लुकअप की गारंटी देती हैं, लेकिन सबसे खराब केस सम्मिलन - हैश बनाने में - ओ (1) नहीं है। किसी भी विशेष हैशिंग डेटा संरचना को देखते हुए, इनपुट के कुछ सेट होंगे जो रोगजनक व्यवहार का उत्पादन करेंगे। मुझे संदेह है कि ओ (एन.एल.एल. (एन)) समय और ओ (एन) अंतरिक्ष के संयुक्त बुरे-मामले [सम्मिलित-एन-तत्वों के बाद लुकअप-एन-तत्व] के साथ हैशिंग डेटा संरचनाएं मौजूद हैं।

Answer 9

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

Answer 10

यहां गहरे पानी पर जा रहे हैं, लेकिन:

छाँटे सूचीबद्ध करता छंटाई O(nlogn) हो सकता है के रूप में बताया। सिर्फ स्पष्टीकरण के लिए, इससे कोई फर्क नहीं पड़ता कि दो सूचियां हैं, क्योंकि: O(2*nlogn) == O(nlogn), फिर प्रत्येक तत्व की तुलना करना एक और ओ (एन) है, इसलिए प्रत्येक तत्व की तुलना करने के बाद दोनों को सॉर्ट करना ओ (एन) + ओ (nlogn) है जो है: O(nlogn)

हैश-टेबल: एक हैश तालिका में पहली सूची परिवर्तित हे (एन) पढ़ने के लिए + हैश तालिका, जो मैं लगता है कि हे के रूप में अनुमान लगाया जा सकता में भंडारण की लागत है (एन) , ओ (एन) देता है। फिर आपको उत्पादित हैश तालिका में दूसरी सूची में प्रत्येक तत्व के अस्तित्व की जांच करनी होगी, जो (कम से कम?) ओ (एन) (यह मानते हुए कि हैश-टेबल तत्व के अस्तित्व की जांच स्थिर है)। सब कुछ, हम चेक के लिए O(n) के साथ समाप्त होते हैं।

जावा सूची इंटरफ़ेस defines equals प्रत्येक संबंधित तत्व बराबर है।

दिलचस्प बात यह है कि जावा संग्रह इंटरफ़ेस परिभाषा almost discourages implementing the equals() फ़ंक्शन।

अंत में, जावा Set interface per documentation implements यह बहुत व्यवहार है। कार्यान्वयन बहुत कुशल होना चाहिए, लेकिन दस्तावेज़ीकरण प्रदर्शन का कोई उल्लेख नहीं करता है। (स्रोत के लिए एक लिंक नहीं मिला, शायद यह सख्ती से लाइसेंस प्राप्त है। इसे डाउनलोड करें और इसे स्वयं देखें। यह जेडीके के साथ आता है) स्रोत को देखते हुए, हैशसेट (जो सेट का एक सामान्य रूप से उपयोग किया जाने वाला कार्यान्वयन है) बराबर() सारणीसेट में कार्यान्वयन, जो हैशसेट से फिर से() फ़ंक्शन का उपयोग करके सार कोलेक्शन के includeAll() फ़ंक्शन का उपयोग करता है। तो HashSet.equals() ओ (एन) में अपेक्षित के रूप में चलता है। (सभी तत्वों के माध्यम से लूपिंग और हैश-टेबल में निरंतर समय में उन्हें देख रहे हैं।)

अगर आप मुझे शर्मिंदगी छोड़ने के लिए बेहतर जानते हैं तो कृपया संपादित करें।

Answer 11

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

Answer 12

यह अलग अलग तरीकों से किया जा सकता है:

1 - ब्रूट बल: array1 में प्रत्येक तत्व के लिए जाँच करें कि तत्व array2 में मौजूद है। ध्यान दें कि इसे स्थिति/अनुक्रमणिका को नोट करने की आवश्यकता होगी ताकि डुप्लीकेट को ठीक से संभाला जा सके। इसके लिए ओ (एन^2) की आवश्यकता बहुत जटिल कोड के साथ है, इसके बारे में भी सोचें ...

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

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

4 - बेस्ट ऑफ बेस्ट (उपरोक्त में): दो सरणी के उसी इंडेक्स में प्रत्येक तत्व का घटाएं या अंतर लें और आखिरकार घटाए गए मानों को जोड़ दें। उदाहरण के लिए ए 1 = {1,2,3}, ए 2 = {3,1,2} डिफ = {- 2,1,1} अब डिफ = 0 का योग करें जिसका अर्थ है कि उनके पास पूर्णांक का एक ही सेट है। इस दृष्टिकोण के लिए एक ओ (एन) की आवश्यकता नहीं है जिसमें कोई अतिरिक्त स्मृति नहीं है। एक सी # कोड के रूप में इस तरह दिखेगा:

public static bool ArrayEqual(int[] list1, int[] list2) 
    { 
     if (list1 == null || list2 == null) 
     { 
      throw new Exception("Invalid input"); 
     } 

     if (list1.Length != list2.Length) 
     { 
      return false; 
     } 

     int diff = 0; 

     for (int i = 0; i < list1.Length; i++) 
     { 
      diff += list1[i] - list2[i]; 
     } 

     return (diff == 0); 
    } 

4 बिल्कुल काम नहीं करता है, यह सबसे खराब

Answer 13

आप आगे इस अनुकूलन करने के लिए एक हस्ताक्षर (सरणी से अधिक सदस्य है विनिमेय आपरेशन) का उपयोग कर सकते है ऐसे मामले में जहां सरणी आमतौर पर अलग होती है, o(n log n) या स्मृति आवंटन को सहेजती है। एक हस्ताक्षर एक ब्लूम फ़िल्टर (ओं) के रूप में हो सकता है, या यहां तक ​​कि एक सरल कम्यूटिव ऑपरेशन जैसे अतिरिक्त या xor।

एक साधारण उदाहरण (एक अच्छा ऑब्जेक्ट पहचानकर्ता के रूप में हस्ताक्षर पक्ष और गेटहाशकोड के रूप में लंबे समय तक मानना; यदि ऑब्जेक्ट्स हैं, कहें, इनट्स, तो उनका मान एक बेहतर पहचानकर्ता है; और कुछ हस्ताक्षर लंबे से बड़े होंगे)

public bool MatchArrays(object[] array1, object[] array2) 
{ 
    if (array1.length != array2.length) 
     return false; 
    long signature1 = 0; 
    long signature2 = 0; 
    for (i=0;i<array1.length;i++) { 
     signature1=CommutativeOperation(signature1,array1[i].getHashCode()); 
     signature2=CommutativeOperation(signature2,array2[i].getHashCode()); 
    } 

    if (signature1 != signature2) 
     return false; 

    return MatchArraysTheLongWay(array1, array2); 
} 

जहां (एक अतिरिक्त आपरेशन का उपयोग करते हुए, एक अलग विनिमेय आपरेशन का उपयोग अगर वांछित, जैसे खिलने फिल्टर)

public long CommutativeOperation(long oldValue, long newElement) { 
    return oldValue + newElement; 
} 

Answer 14

यहाँ एक और विकल्प है, मुझे पता है कि तुम लोगों think.It टी होना चाहिए जाने (एन) = 2 एन * log2n -> ओ (nLogn) सबसे खराब मामले में।

private boolean compare(List listA, List listB){ 
    if (listA.size()==0||listA.size()==0) return true; 
    List runner = new ArrayList(); 
    List maxList = listA.size()>listB.size()?listA:listB; 
    List minList = listA.size()>listB.size()?listB:listA; 
    int macthes = 0; 
    List nextList = null;; 
    int maxLength = maxList.size(); 
    for(int i=0;i<maxLength;i++){ 
     for (int j=0;j<2;j++) { 
      nextList = (nextList==null)?maxList:(maxList==nextList)?minList:maList; 
      if (i<= nextList.size()) { 
       MatchingItem nextItem =new MatchingItem(nextList.get(i),nextList) 
       int position = runner.indexOf(nextItem); 
       if (position <0){ 
        runner.add(nextItem); 
       }else{ 
        MatchingItem itemInBag = runner.get(position); 
        if (itemInBag.getList != nextList) matches++; 
        runner.remove(position); 
       } 
      } 
     } 
    } 
    return maxLength==macthes; 
} 

public Class MatchingItem{ 
private Object item; 
private List itemList; 
public MatchingItem(Object item,List itemList){ 
    this.item=item 
    this.itemList = itemList 
} 
public boolean equals(object other){ 
    MatchingItem otheritem = (MatchingItem)other; 
    return otheritem.item.equals(this.item) and otheritem.itemlist!=this.itemlist 
} 

public Object getItem(){ return this.item} 
public Object getList(){ return this.itemList} 

}

Answer 15

स्यूडोकोड:

A:array 
B:array 
C:hashtable 

if A.length != B.length then return false; 

foreach objA in A 
{ 
H = objA; 
if H is not found in C.Keys then 
C.add(H as key,1 as initial value); 
else 
C.Val[H as key]++; 
} 

foreach objB in B 
{ 
H = objB; 
if H is not found in C.Keys then 
return false; 
else 
C.Val[H as key]--; 
} 

if(C contains non-zero value) 
return false; 
else 
return true; 

Answer 16

एक सरणी के तत्वों के अलग रूप में दिया जाता है, तो XOR (बिटवाइज़ XOR) सभी दोनों सरणियों के तत्वों, अगर जवाब है शून्य, तो दोनों सरणी संख्याओं का एक ही सेट है। समय जटिलता ओ (एन)