Intersezione di due array con ripetizione

Question

Sto provando a creare un metodo che prevede l'intersezione di due array con ripetizione.

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

Ho un metodo che fa intersezione ma senza ripetizione.

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; 
    } 

Come posso aggiungere ripetizioni senza usare Arrays.* o List.*?

Answer 1

Prova seguente funzione:

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; 
} 

Se necessario si dovrebbe anche applicare l'ordinamento, questa soluzione ha O (N^2) la complessità. Anche possibile complessità O (NLogN).

Answer 2

È possibile costruire un histogram (sarà rappresentato come un Map<Integer,Integer>) e:

1. Inserire tutti gli elementi (e il numero delle loro ripetizioni) dal List1 per l'istogramma
2. lista2 Iterate per ogni elemento e :
   - se l'istogramma contiene l'elemento di posta (con valore positivo): stampa (o aggiungere a un nuovo elenco) e, e diminuire il valore per l'e nell'istogramma

Nota questa soluzione è il tempo O(n+m) (caso medio) e lo spazio O(min{n,m}).

---

campione Codice (usando List<T> al posto di un array - ma può essere facilmente modificata, ovviamente):

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)); 
} 

---

Nota può anche essere fatto in O(nlogn) tempo e O(logn) spazio (per la traccia di stack dell'algoritmo di ordinamento) con l'ordinamento degli elenchi e quindi l'iterazione in parallelo con un puntatore per ogni elenco

Codice

pseudo:

Ripetere mentre i1 < list1.length e i2 < list2.length:

1. se lista1 [i1] == lista2 [i2]:
   - stampa lista1 [i1 ]
   - aumento i1, i2
2. altrimenti se lista1 [i1]> lista2 [i2]:
   - aumento i2
3. altro:
   - aumento i1

Answer 3

C'è un motivo per non utilizzare le raccolte? Il metodo retainAll(...) fa ciò che si vuole:

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

Answer 4

Un modo per farlo è utilizzare le tabelle hash. Crea due tabelle hash separate dai due array. Le coppie di valori chiave sono (elemento, numero). Ora passa attraverso la tabella hash più piccola e stampa ogni elemento count_min numero di volte in cui count_min = min (conteggio dell'elemento nella tabella a, conteggio dell'elemento nella tabella b). Questo è un algoritmo lineare con una complessità spaziale aggiuntiva.

Complessità dello spazio = O (n + m) dove n e m sono le dimensioni dei due array. Tempo complesso O (n) dove n> m.