查找数组中添加/删除元素的算法

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] <b [y],则删除[x](并且只增加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

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