Kreuzung von zwei Arrays mit Wiederholung

Question

Ich versuche, eine Methode zu erstellen, die Kreuzung von zwei Arrays mit Wiederholung tut.

Beispiel: {1,2,5,4,1,3} and {1,2,1} -> {1,1,2}.

Ich habe ein Verfahren, das Schnitt tut, aber ohne Wiederholung.

public int[] findSameElements(int[] p1, int[] p2) { 
    int count = 0; 
    for (int i = 0; i < p1.length; i++) { 
     for (int j = 0; j < p2.length; j++) { 
     if (p1[i] == p2[j]) { 
      count++; 
      break; 
     } 
     } 
    } 

    int[] result = new int[count]; 
    count = 0; 
    for (int i = 0; i < p1.length; i++) { 
     for (int j = 0; j < p2.length; j++) { 
     if (p1[i] == p2[j]) { 
      result[count++] = p1[i]; 
      break; 
     } 
     } 
    } 

    return result; 
    } 

Wie kann ich Wiederholungen hinzufügen, ohne Arrays.* oder List.* zu verwenden?

Answer 1

Bitte versuchen Sie folgende Funktion:

public int[] findSameElements(int[] p1, int[] p2) 
{ 
    int count = 0; 
    bool[] choosen = new bool[p2.length]; 

    for (int i = 0; i < p1.length; i++) 
    { 
     for (int j = 0; j < p2.length; j++) 
     { 
      if (!choosen[j] && p1[i] == p2[j]) 
      { 
       choosen[j] = true; 
       count++; 
       break; 
      } 
     } 
    } 

    int[] result = new int[count]; 
    count = 0; 
    for (int i = 0; i < p2.length; i++) 
    { 
     if (choosen[i]) 
     { 
      result[count] = p2[i]; 
      count++; 
     } 
    } 

    return result; 
} 

Bei Bedarf sollten Sie auch Sortierung anwenden, diese Lösung hat O (N^2) Komplexität. Auch möglich gemacht O (NLogN) Komplexität.

Answer 2

Sie können bauen eine histogram (wird als Map<Integer,Integer> dargestellt werden) und:

1. Legen Sie alle Elemente (und die Zahl ihrer Wiederholungen) von list1 zu dem Histogramm
2. Iterate list2 für jedes Element e :
   - wenn das Histogramm enthält das Element e (mit positivem Wert): print (oder zu einer neuen Liste anhänge) e und den Wert für e in dem Histogramm

Hinweis verringern dass diese Lösung O(n+m) Zeit (durchschnittlicher Fall) und O(min{n,m}) Platz ist.

---

Codebeispiel (List<T> anstelle eines Arrays mit - aber es kann leicht natürlich geändert werden):

private static <T> Map<T,Integer> populateHistogram(List<T> list) { 
    Map<T,Integer> histogram = new HashMap<T, Integer>(); 
    for (T e : list) { 
     Integer val = histogram.get(e); 
     histogram.put(e, val == null ? 1 : val+1); 
    } 
    return histogram; 
} 
public static <T> List<T> generateInterectionList(List<T> list,Map<T,Integer> histogram) { 
    List<T> res = new ArrayList<T>(); 
    for (T e : list) { 
     Integer val = histogram.get(e); 
     if (val != null && val > 0) { 
      res.add(e); 
      histogram.put(e,val - 1); 
     } 
    } 
    return res; 
} 
public static <T> List<T> getIntersection(List<T> list1, List<T> list2) { 
    Map<T,Integer> histogram = populateHistogram(list1.size() > list2.size() ? list2 : list1); 
    return generateInterectionList(list1.size() > list2.size() ? list2 : list1,histogram); 
} 
public static void main(String[]args){ 
    List<Integer> list1 = Arrays.asList(new Integer[]{1,2,5,4,1,3}); 
    List<Integer> list2 = Arrays.asList(new Integer[]{1,2,1}); 
    System.out.println(getIntersection(list1, list2)); 
} 

---

Hinweis kann es auch in O(nlogn) Zeit und O(logn) erfolgen Leerzeichen (für Stack-Trace des Sortieralgorithmus) mit Sortieren der Listen und dann Iterieren parallel mit einem Zeiger für jede Liste

Pseudocode:

Repeat während i1 < list1.length und i2 < list2.length:

1. wenn list1 [i1] == list2 [i2]:
   - print list1 [i1 ]
   - Erhöhung i1, i2
2. else if list1 [i1]> list2 [i2]:
   - Erhöhung i2
3. anderes:
   - erhöhen i1

Answer 3

Gibt es einen Grund, Sammlungen nicht zu verwenden? Die retainAll(...) Methode tut, was Sie wollen:

List<Integer> list1 = ... 
List<Integer> list2 = ... 
List<Integer> intersection = list1.retainAll(list2); 

Answer 4

Eine Möglichkeit ist die Verwendung von Hashtabellen. Erstellen Sie zwei separate Hash-Tabellen aus den beiden Arrays. Die Schlüsselwertpaare sind (Element, Anzahl). Gehen Sie nun durch die kleinere Hash-Tabelle und drucken Sie jedes Element count_min Anzahl der Male aus, wobei count_min = min (Anzahl der Elemente in Tabelle a, Anzahl der Elemente in Tabelle b). Dies ist ein linearer Algorithmus mit einer zusätzlichen Raumkomplexität.

Raumkomplexität = O (n + m) wobei n und m die Größen der beiden Arrays sind. Zeitkomplex O (n) mit n> m.