一千萬個為什麽

搜索

查找數組中添加/刪除元素的算法

我正在尋找解決以下問題的最有效方法

問題:

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

有沒有人知道更好的解決方案可能更有效,並且不會覆蓋原始數組

最佳答案

排序是你的朋友。

對兩個數組(a和b)進行排序,然後遍歷它們(使用x和y作為計數器)。一次向下移動1。您可以從那裏派生所有測試:

  • if a[x] < b[y], then a[x] was removed (and only increment x)
  • if a[x] > b[y], then b[y] was added (and only increment y)

(我可能錯過了一個邊緣案例,但你得到了一般的想法。)

(編輯:這裏沒有涉及的主要邊緣情況是當你在另一個數組之前到達其中一個數組的末尾時處理,但是要弄清楚並不難。:)

轉載註明原文: 查找數組中添加/刪除元素的算法