Suche nach gemeinsamen Elemente in beiden arrays unterschiedlicher Größe

Ich habe ein problem, finde gemeinsame Elemente in zwei arrays, und das ist von unterschiedlicher Größe.

Nehmen , Array A1 Größe n - und Array - A2 Größe mund m != n

So weit, ich habe versucht, zu iterieren von Listen und kopieren von Elementen zu einer anderen Liste. Wenn das element bereits enthält, markieren Sie es, aber ich weiß, es ist keine gute Lösung.

InformationsquelleAutor der Frage Jijoy | 2010-12-25

  1. 28

    Sortieren der arrays. Dann Durchlaufen Sie mit zwei Zeigern, immer vorantreiben der eine zeigt auf den kleineren Wert. Wenn Sie verweisen auf die gleichen Werte, Sie haben einen gemeinsamen Wert. Dies wird O(n+m), wobei n und m sind die Größen der beiden Listen. Es ist wie ein verschmelzen in merge-sortsondern wo Sie produzieren nur Ausgabe, wenn die Werte zu wies zu gleich sind.

    def common_elements(a, b):
  a.sort()
  b.sort()
  i, j = 0, 0
  common = []
  while i < len(a) and j < len(b):
    if a[i] == b[j]:
      common.append(a[i])
      i += 1
      j += 1
    elif a[i] < b[j]:
      i += 1
    else:
      j += 1
  return common

print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))

    Ausgänge

    Common values: 1, 4

    Wenn die Elemente nicht vergleichbar sind, werfen Sie die Elemente von einer Liste in eine hashmap und überprüfen Sie die Elemente in der zweiten Liste gegen die hashmap.

    InformationsquelleAutor der Antwort marcog

  2. 12

    Wenn Sie wollen, um es effizient würde ich konvertieren Sie das kleinere array in ein hashset und dann Durchlaufen der größeren array und prüfen, ob das aktuelle element enthalten war, in das hashset. Die hash-Funktion ist effizienter im Vergleich zur Sortierung von arrays. Sortieren von arrays ist teuer.

    Hier ist mein Beispielcode

    import java.util.*;
public class CountTest {     
    public static void main(String... args) {        
        Integer[] array1 = {9, 4, 6, 2, 10, 10};
        Integer[] array2 = {14, 3, 6, 9, 10, 15, 17, 9};                    
        Set hashSet = new HashSet(Arrays.asList(array1)); 
        Set commonElements = new HashSet();        
        for (int i = 0; i < array2.length; i++) {
            if (hashSet.contains(array2[i])) {
                commonElements.add(array2[i]);
            }
        }
        System.out.println("Common elements " + commonElements);
    }    
}

    Ausgabe:

    Gemeinsame Elemente [6, 9, 10]

    InformationsquelleAutor der Antwort Jacorb Effect

  3. 1

    In APL:

    ∪A1∩A2

    Beispiel:

          A1←9, 4, 6, 2, 10, 10
      A1
9 4 6 2 10 10

      A2←14, 3, 6, 9, 10, 15, 17, 9
      A2
14 3 6 9 10 15 17 9

      A1∩A2
9 6 10 10
      ∪A1∩A2
9 6 10

    InformationsquelleAutor der Antwort StackPC

  4. 0

    Sieht aus wie nested loops:

    commons = empty
for each element a1 in A1
   for each element a2 in A2
      if a1 == a2
         commons.add(a1)

    Schouldn alles nichts, wenn die arrays haben die gleiche Größe.

    Je nach Sprache und framework, das verwendet wird, set-Operationen in handliches kommen könnte.

    InformationsquelleAutor der Antwort Eiko

  5. 0

    Versuchen heapifying beiden arrays, gefolgt von einem merge zu finden, um die Kreuzung.

    Java-Beispiel:

    public static <E extends Comparable<E>>List<E> intersection(Collection<E> c1,
                                                            Collection<E> c2) {
    List<E> result = new ArrayList<E>();
    PriorityQueue<E> q1 = new PriorityQueue<E>(c1),
                     q2 = new PriorityQueue<E>(c2);
    while (! (q1.isEmpty() || q2.isEmpty())) {
        E e1 = q1.peek(), e2 = q2.peek();
        int c = e1.compareTo(e2);
        if (c == 0) result.add(e1);
        if (c <= 0) q1.remove();
        if (c >= 0) q2.remove();
    }
    return result;
}

    Sehen diese Frage weitere Beispiele für die Zusammenführung.

    InformationsquelleAutor der Antwort finnw

  6. 0

    Die Komplexität dessen, was ich gebe ist O(N*M + N).

    Beachten Sie auch, dass es Pseudocode C Und dass es unterschiedliche Werte.

    zB.[1,1,1,2,2,4] und [1,1,1,2,2,2,5] zurück [1,2]

    Die Komplexität ist
    N*M Ursache des for Schleifen

    + N Ursache für die Prüfung, ob es bereits in der ArrayCommon[] (das ist n Größe bei Array2[] Daten enthält, die doppelte Teil des Array1[] Vorausgesetzt, N ist die Größe der kleineren Array (N < M).

    int Array1[m] = { Whatever };
int Array2[n] = { Whatever };
int ArrayCommon[n] = { };

void AddToCommon(int data)
{
    //How many commons we got so far?
    static int pos = 0; 
    bool found = false;
    for(int i = 0 ; i <= pos ; i++)
    {
        //Already found it?
        if(ArrayCommon[i] == data)
        {
            found = true;
        }
    }
    if(!found)
    {
        //Add it
        ArrayCommon[pos] = data;
        pos++;
    }
}

for(int i = 0 ; i < m ; i++)
{
    for(int j = 0 ; j < n ; j++)
    {
        //Found a Common Element!
        if(Array1[i] == Array2[j])
            AddToCommon(Array1[i]);
    }
}

    InformationsquelleAutor der Antwort Muggen

  7. 0

    In Python, schreiben Sie set(A1).intersection(A2). Dies ist die optimale O(n + m).

    Gibt es die Zweideutigkeit, die in Ihrer Frage wenn. Was ist das Ergebnis von A1=[0, 0], A2=[0, 0, 0]? Es gibt vernünftige Interpretationen Ihrer Frage, geben Sie 1, 2, 3, oder 6 Ergebnisse in der letzten array - was ist Ihre situation benötigen?

    InformationsquelleAutor der Antwort

  8. 0

    Ich das problem lösen, indem mit Set-Kreuzung. Es ist sehr elegant. Auch wenn ich nicht analysieren Sie die Zeitkomplexität ist es wohl im angemessenen Bereich.

    public Set FindCommonElements(Integer[] first, Integer[] second)
{

    Set<Integer> set1=new HashSet<Integer>(Arrays.asList(first));
    Set<Integer> set2=new HashSet<Integer>(Arrays.asList(second));

    //finds intersecting elements in two sets
    set1.retainAll(set2);

    return set1;

}

    InformationsquelleAutor der Antwort alan turing

  9. -2
    class SortedArr

    def findCommon(a,b)

      j =0
      i =0
      l1=a.length
      l2=b.length

      if(l1 > l2)
            len=l1
      else
            len=l2
      end


     while i < len
          if a[i].to_i > b[j].to_i
              j +=1
          elsif a[i].to_i < b[j].to_i
              i +=1
          else   
              puts a[i] # OR store it in other ds
              i +=1
              j +=1
          end
     end
  end
end

 t = SortedArr.new
 t.findCommon([1,2,3,4,6,9,11,15],[1,2,3,4,5,12,15])

    InformationsquelleAutor der Antwort user2476720

Schreibe einen Kommentar