Алгоритм поиска добавленных / удаленных элементов в массиве

Question

Я ищу наиболее эффективный способ решения следующих проблем

Проблема:

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

Моя идея пока такова:

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

Кто-нибудь знает лучшее решение, возможно, более эффективное, и оно не переписывает исходные массивы

Answer 1

Сортировка - твой друг.

Сортируйте два массива (a и b), а затем обойдите их (используя x и y в качестве счетчиков). Двигайтесь вниз по 1 за раз. Вы можете получить все свои тесты оттуда:

• если a [x] если a [x]> b [y], то был добавлен b [y] (и только приращение y)

(Возможно, я пропустил крайний случай, но вы поняли основную идею.)

(правка: случай первичного края, который здесь не рассматривается, обрабатывается, когда вы достигаете конца одного из массивов раньше другого, но это не сложно понять.

Answer 2

Вы также можете использовать Dictionary<int, int> и алгоритм, подобный следующему:

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

Последний словарь сообщает вам, какие элементы были вставлены / удалены (и как часто). Это решение должно быть довольно быстрым даже для больших списков - быстрее, чем сортировка.

Answer 3

если ваш язык доступен как мультимножество (задано с количеством элементов), ваш вопрос является стандартной операцией.

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

результат - A.symdiff (B) (symdiff - объединение минус пересечение, и это именно то, что вы ищете, чтобы удалить и добавить).

Очевидно, что вы также можете быть удалены или добавлены только с использованием классической разницы между наборами.

Это может быть тривиально реализовано с использованием хэшей, и это O (n) (использование сортировки немного менее эффективно, чем O (n.log (n)) из-за самой сортировки).

Answer 4

Это можно решить за линейное время. Создайте карту для расчета количества повторений каждого элемента. Пройдите через массив before и заполните карту. Пройдите через массив after и уменьшите значение на карте для каждого элемента. В конце пройдите по карте, и если вы найдете отрицательное значение, этот элемент был добавлен - если положительный, этот элемент был удален.

Вот некоторый Java-код для этого (не тестировался, только что написан прямо сейчас):

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 5

В каком-то 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 6

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

Результат:

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]

Для countBy Я получил отклик от Какой-то отличный волшебный пост

В groovy inject похож на reduce в других функциональных языках.

Я также имею в виду Слайды API Groovy из коллекции Trygve Amundsen с действительно хорошим столом с функциональными методами

Второе решение:

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

Answer 7

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

результат:

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