Алгоритм для нахождения добавил/удалил элементы в массиве
Я ищу большую часть efficent способа решить следующее
Проблема:
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
Делает любой знает лучшее решение, возможно, больше efficent, и это не перезаписывает исходные массивы
5 ответов
Вы также можете использовать Dictionary и алгоритм, подобный этому:
foreach i in source_list: dictionary[i]++;
foreach i in dest_list: dictionary[i]--;
Последний словарь сообщает вам, какие элементы были вставлены / удалены (и Как часто). Это решение должно быть довольно быстрым даже для больших списков - быстрее, чем сортировка.
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
если ваш язык доступен как мультимножество (задано с количеством элементов), ваш вопрос является стандартной операцией.
B = multiset(Before)
A = multiset(After)
результатом является A.symdiff (B) (symdiff - это объединение минус пересечение, и это именно то, что вы хотите удалить и добавить).
Очевидно, вы также можете быть только удалены или добавлены только с использованием классической разницы между наборами.
Это может быть тривиально реализовано с использованием хешей, и это O (n) (использование sort немного менее эффективно, поскольку это O (n.log (n)) из-за самой сортировки).
Сортировка - ваш друг.
Отсортируйте два массива (a и b), а затем пройдитесь по ним (используя x и y в качестве счетчиков). Двигайтесь вниз по одной за раз. Отсюда вы можете получить все свои тесты:
- если a [x]
- , если a [x]> b [y], затем был добавлен b [y] (и только приращение y)
(возможно, я пропустил крайний случай, но вы поняли общую идею.)
(редактирование: первичный крайний случай, который здесь не рассматривается, это обработка, когда вы достигаете конца одного из массивов раньше другого, но это несложно понять. :)
В каком-то псевдокоде 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]);
}