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

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

排序是你的 friend 。

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

• 如果 a[x] < b[y]，则删除 a[x](并且只增加 x)
• 如果 a[x] > b[y]，则添加 b[y](并且只增加 y)

(我可能错过了一个边缘案例，但你明白了总体思路。)

(编辑:此处未涵盖的主要边缘情况是当您先于另一个数组到达一个数组的末尾时进行处理，但这并不难弄清楚。:)