/elementi Algoritmo per trovare aggiunto rimossi in un array

Question

sto cercando il modo più efficiente per risolvere il seguente

Problema:

given an array Before = { 8, 7, 2, 1} and an array After ={1, 3, 8, 8} 
find the added and the removed elements 

the solution is: 
     added = 3, 8 
     removed = 7, 2 

La mia idea finora è:

for i = 0 .. B.Lenghtt-1 
{ 
    for j= 0 .. A.Lenght-1 
    { 
     if A[j] == B[i] 

      A[j] = 0; 
      B[i] = 0; 

      break; 
    } 
} 

// B elemnts different from 0 are the Removed elements 
// A elemnts different from 0 are the Added elemnts 

Qualcuno sa una soluzione migliore forse più efficace e che non sovrascrive gli array originali

Answer 1

In una sorta di codice C++ pseudo:

Before.sort(); 
After.sort(); 
int i = 0; 
int j = 0; 
for (; i < Before.size() && j < After.size();) { 
    if (Before[i] < After[j]) { 
     Removed.add(Before[i]); 
     ++i; 
     continue; 
    } 
    if (Before[i] > After[j]) { 
     Added.add(After[j]); 
     ++j; 
     continue; 
    } 
    ++i; 
    ++j; 
} 
for (; i < Before.size(); ++i) { 
    Removed.add(Before[i]); 
} 
for (; j < After.size(); ++j) { 
    Added.add(After[j]); 
} 

Answer 2

ordinamento è tuo amico.

Ordinare i due array (a e b), quindi eseguirne il movimento (utilizzando xey come contatori). Sposta giù entrambi 1 alla volta. È possibile derivare tutti i test da lì:

• se un [x] < b [y], poi una [x] è stato rimosso (e solo incremento x)
• se un [x]> b [ y], quindi b [y] è stata aggiunta (e solo incremento y)

(io possa aver perso un caso limite, ma si ottiene l'idea generale.)

(edit: il caso limite primario non è coperto qui è la gestione quando si raggiunge la fine di uno degli array prima dell'altra, ma non è difficile da capire. :)

Answer 3

Si potrebbe anche usare un algoritmo Dictionary<int, int> e una simile a questo:

foreach i in source_list: dictionary[i]++; 
foreach i in dest_list: dictionary[i]--; 

Il dizionario finale si che sono state inserite/rimosse (e quanto spesso) elementi dice. Questa soluzione dovrebbe essere abbastanza veloce anche per gli elenchi più grandi, più veloce dell'ordinamento.

Answer 4

se la tua lingua come multiset è disponibile (impostata con il conteggio di elementi) la tua domanda è un'operazione standard.

B = multiset(Before) 
A = multiset(After) 

risultato è A.symdiff (B) (symdiff è l'unione meno di intersezione e questo è esattamente quello che stai cercando per aver rimosso e aggiunto).

Ovviamente è possibile anche solo rimuovere o aggiungere solo utilizzando la classica differenza tra le serie.

Può essere implementato banalmente usando gli hash ed è O (n) (l'ordinamento è leggermente meno efficiente in quanto è O (n.log (n)) a causa dell'ordinamento stesso).

Answer 5

Perl:

 
@a = (8, 7, 2, 2, 1); 
@b = (1, 3, 8, 8, 8); 

$d{$_}++ for(@a); 
$d{$_}-- for(@b); 

print"added = "; 
for(keys %d){print "$_ " x (-$d{$_}) if($d{$_}<0)} 
print"\n"; 
print"removed = "; 
for(keys %d){print "$_ " x ($d{$_}) if($d{$_}>0)} 
print"\n"; 

risultato:

 
$ ./inout.pl 
added = 8 8 3 
removed = 7 2 2 

Answer 6

Questo può essere risolto in tempo lineare. Creare una mappa per calcolare il numero di ripetizioni di ciascun elemento. Attraversa l'array before e riempi la mappa. Passare attraverso la matrice after e diminuire il valore nella mappa per ciascun elemento. Alla fine, passa attraverso la mappa e se trovi un valore negativo, quell'elemento è stato aggiunto - se positivo, quell'elemento è stato rimosso.

Ecco il codice Java per questo (non testato, appena scritto in questo momento):

Map<Integer, Integer> repetitionMap = new HashMap<Integer, Integer>(); 

for (int i = 0; i < before.length; i++) { 
    Integer number = repetitionMap.get(before[i]); 
    if (number == null) { 
     repetitionMap.put(before[i], 1); 
    } else { 
     repetitionMap.put(before[i], number + 1); 
    } 
} 

for (int i = 0; i < after.length; i++) { 
    Integer number = repetitionMap.get(after[i]); 
    if (number == null) { 
     repetitionMap.put(after[i], -1); 
    } else { 
     repetitionMap.put(after[i], number - 1); 
    } 
} 

Set<Integer> keySet = repetitionMap.keySet(); 
for (Integer i : keySet) { 
    Integer number = repetitionMap.get(i); 
    if (number > 0) { 
     System.out.println("removed " + number + "times value " + i); 
    } 

    if (number < 0) { 
     System.out.println("added " + number + "times value " + i); 
    } 
} 

Answer 7

in Groovy:

def before = [8, 7, 2, 1, 1, 1], after = [1, 3, 8, 8, 8] 
def added = before.countBy{it} 
def result = after.inject(added){map, a -> map[a] ? map << [(a):map[a] - 1]: map << [(a):-1]} 
     .inject([:]){m, k, v -> v == 0 ? (m << [:]) : (v < 0 ? m << [(k):"added ${v.abs()} times"] : m << [(k):"removed ${v.abs()} times"])} 
println "before $before\nafter $after" 
println "result: $result" 

Risultato:

before [8, 7, 2, 1, 1, 1] 
after [1, 3, 8, 8, 8] 
result: [8:added 2 times, 7:removed 1 times, 2:removed 1 times, 1:removed 2 times, 3:added 1 times] 

Per countBy I ottenuto un insipred da Some groovy magic post

In groove inject è come reduce in altri linguaggi funzionali.

Ho anche rimando Groovy collection api slides from Trygve Amundsen con molto buon tavolo con metodi funzionali

Seconda soluzione:

def before = [8, 7, 2, 1, 1, 1], after = [1, 3, 8, 8, 8] 
def sb = before.countBy{it} 
def sa = after.countBy{it} 
def result = sa.inject(sb){m, k, v -> m[k] ? m << [(k): m[k] - v] : m << [(k): -v]} 
    .inject([:]){m, k, v -> v == 0 ? (m << [:]) : (v < 0 ? m << [(k):"added ${v.abs()} times"] : m << [(k):"removed ${v.abs()} times"])}