寻找数组中新增/删除元素的算法

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

有人知道一种更好的解决方案吗？也许更有效，并且不会覆盖原始数组。

- jj.

---

如果将3和8相加并移除7、2、1，则“数组后”应为{3, 8, 8}或{1, 3, 8, 8}。 - kennytm

"After" 数组中不能存在 "1"。你一开始只有一个 "1"，你将其移除并且不再添加回去，那么为什么在 After 数组中还会出现呢？你应该修正你的示例。 - Cosmin Prund

我经常犯的错误，我已经纠正了。谢谢，jj。 - jj.

Answer 1

排序是你的好朋友。

对两个数组(a和b)进行排序，然后遍历它们(使用x和y作为计数器)。每次都向下移动1步。你可以从那里推导出所有的测试:

• 如果a[x] < b[y]，则a[x]被删除了（只增加x）
• 如果a[x] > b[y]，则b[y]被添加了（只增加y）

(我可能错过了某些边缘情况，但你可以理解我的意思。)

(编辑: 这里没有涉及到的主要边缘情况是当一个数组提前到达尾部时如何处理，但这并不难解决。 :)

- Joe

---

感谢Joe、Andreas和Kriss。最后检查一下，从效率上来说，你的解决方案成本是n log(n) + n log(n) + n = O (n log n)。因此，在处理这种问题时，总是建议先进行排序，对吧？jj - jj.

@jj：基本上是的，提前排序更好。在这种特殊情况下，您还可以使用哈希避免排序，因为您不需要顺序，而只需要知道该项是否存在。 - kriss

我也更喜欢哈希表，因为它具有较低复杂度Theta(N)。 - Matthieu M.

Joe和Andreas，你们是怎么发现这个算法的？你们能否阐述一下你们的思考过程，并解释一下为什么排序数组和那种扫描方式会证明是高效的呢？jj - jj.

Answer 2

您也可以使用 Dictionary<int, int> 和类似于以下算法的算法：

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

最终的字典会告诉你哪些元素被插入/删除（以及出现的次数）。即使在更大的列表中，这种解决方案也应该相当快 —— 比排序更快。

- mafu

Answer 3

如果您的语言支持multiset（包含元素计数的集合），那么您的问题就是一个标准操作。

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

结果是A.symdiff(B)（symdiff是并集减去交集，这正是您要删除和添加的内容）。

显然，您还可以使用集合之间的经典差异仅获取已删除或已添加的内容。

它可以使用哈希轻松实现，并且它是O(n)的（使用排序略微不太有效，因为它本身是O(n.log(n))）。

- kriss

Answer 4

在某种形式的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]);
}

- Andreas Brinck

Answer 5

这个问题可以在线性时间内解决。 创建一个用于计算每个元素重复次数的映射表。 遍历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);
    }
}

- Marko Ciric

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魔法文章的启发。

在Groovy中，inject类似于其他函数式语言中的reduce。

我还参考了Trygve Amundsen的Groovy集合API幻灯片，其中有一个非常好的功能方法表格。

第二种解决方案：

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

- David

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

- Oleg Razgulyaev

---

这不是一个代码高尔夫比赛的参赛作品！说真的，Perl 有时候很难懂，所以请使用一种更简单的语言（或伪代码）来说明您想要分享的算法。即使问题很简单，我也很难理解您在这里做什么。 - Matthieu M.