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

Question

我正在尋找解決以下

問題的最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 

有沒有人知道更好的解決方案，也許更高效，並且不會覆蓋原始陣列

Answer 1

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

Answer 2

排序是你的朋友。

對兩個數組（a和b）進行排序，然後將它們移走（使用x和y作爲計數器）。一次下移兩個。你可以從那裏得到所有的測試：

• 如果[X] < B [Y]，則[X]移除（只有增量X）
• 如果[X]> B [ Y]，則b [Y]加入（只有增量Y）

（我可能已經錯過了一個邊緣的情況下，但你的總體思路。）

（編輯：主邊緣的情況下這裏沒有涉及到的是當你到達其中一個陣列的末端時處理另一個陣列的結束，但這並不難。:)

Answer 3

你也可以使用一個類似於此Dictionary<int, int>和算法：

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

最終的字典告訴你哪些元素插入/刪除（和頻率）。即使對於更大的列表，此解決方案也應該相當快 - 比排序更快。

Answer 4

如果您的語言爲multiset可用（設置了元素數）您的問題是標準操作。

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

結果是A.symdiff（B）（symdiff是集減交集而這正是你所尋找的已刪除和添加）。

很明顯，您也可以僅刪除或僅使用經典集之間的區別添加。

它可以使用散列來實現，它是O（n）（由於排序本身，使用排序的效率稍低於O（n.log（n）））。

Answer 5

的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 

Answer 6

這可以在線性時間內解決。 創建一個圖來計算每個元素的重複次數。 通過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); 
    } 
} 

Answer 7

在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我從Some groovy magic post

在groovy inject就像reduce在其他功能語言。

我也與真的好表參閱Groovy collection api slides from Trygve Amundsen具有功能的方法

第二溶液：

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