algorithme pour trouver ajoutés/éléments supprimés dans un tableau

Question

Je cherche la façon la plus efficent de résoudre le

problème suivant:

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 

Mon idée à ce jour est:

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 

Est-ce que quelqu'un connaît une meilleure solution peut-être plus efficace et qui n'écrase pas les tableaux d'origine

Answer 1

Dans une sorte de code pseudo de C:

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

Le tri est votre ami.

Triez les deux tableaux (a et b), puis faites-les marcher (en utilisant x et y comme compteurs). Descendez les deux 1 à la fois. Vous pouvez déduire tous vos tests à partir de là:

• si un [x] < b [y], alors [x] a été supprimé (et seulement incrément x)
• si un [x]> b [ y], puis b [y] a été ajouté (et y incrément seulement)

(je peut-être manqué un cas limite, mais vous avez l'idée générale.)

(edit: le cas de bord primaire ce qui n'est pas couvert ici est la manipulation lorsque vous arrivez à la fin de l'un des tableaux avant l'autre, mais ce n'est pas difficile à comprendre.)

Answer 3

Vous pouvez également utiliser un Dictionary<int, int> et un algorithme similaire à ceci:

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

Le dictionnaire final, vous indique quels éléments ont été insérés/enlevés (et la fréquence). Cette solution devrait être assez rapide, même pour les plus grandes listes - plus rapide que le tri.

Answer 4

Si votre langage multiset est disponible (avec le nombre d'éléments), votre question est une opération standard.

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

résultat

est A.symdiff (B) (symdiff est l'union intersection moins et qui est exactement ce que vous cherchez à avoir retiré et ajouté).

Évidemment, vous pouvez également obtenir supprimé uniquement ou ajouté uniquement en utilisant la différence classique entre les ensembles.

Il peut trivialement être implémenté en utilisant des hachages et c'est O (n) (utiliser le tri est légèrement moins efficace car c'est O (n.log (n)) à cause du tri lui-même).

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

résultat:

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

Answer 6

Ceci peut être résolu dans le temps linéaire. Créer une carte pour calculer le nombre de répétitions de chaque élément. Parcourez le tableau before et remplissez la carte. Parcourez le tableau after et diminuez la valeur dans la carte pour chaque élément. À la fin, parcourez la carte et si vous trouvez une valeur négative, cet élément a été ajouté - si positif, cet élément a été supprimé.

Voici un code Java pour cette (non testé, vient d'écrire en ce moment):

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

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" 

Résultat:

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] 

Pour countBy I obtenu insipred de Some groovy magic post

Dans groovy inject est comme reduce dans d'autres langages fonctionnels.

Je me réfère également Groovy collection api slides from Trygve Amundsen avec table très bonne avec des méthodes fonctionnelles

Deuxième solution:

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"])}