algorithm - 前後のセットで何が変わったのか

Question

これはインタビューの質問です: 前: {3, 3, 5, 8, 1} と後: {5, 3, 2, 4} の 2 つの配列が与えられます。「後」を取得するために、「前」配列から削除/追加された番号を特定します。

as を使用して各リストに 2 つのハッシュマップを使用し、それぞれを比較して、各要素が追加または削除されたかどうかを判断することを考えることができます。

誰かがこれに対してより良いアプローチを考えたり、別の解決策 (時間/空間の複雑さを改善したもの) を提供したりできますか?

Answer 1

あなたが提案する答え（2つのハッシュマップを使用）は、可能な限り最良の結果、つまりO（n + m）だと思います。これは、各配列の各要素に少なくとも1回アクセスする必要があるためです。

概念を示すための C# の実装を次に示します。

var b = new [] {3, 3, 5, 8, 1}.ToLookup(k => k);
var a = new [] {5, 3, 2, 4}.ToLookup(k => k);

b.Select(k => k.Key)
 .Concat(a.Select(k => k.Key))
 .Distinct()
 .ToDictionary(k => k, v => (a.Contains(v) ? a[v].Count() : 0) - (b.Contains(v) ? b[v].Count() : 0))
 .Dump(); // linqpad

簡潔にするために多くの linq を使用しました。ループと HashSets で同等のものを使用して書き直す方が効率的でしょう。

Answer 2

各リストをバッグに保存してから、バッグ内の各項目タイプの発生の変化を見つけることができます。

ここにいくつかのPythonがあります：

>>> # Original data
... l1, l2 = [3,3,5,8,1], [5,3,2,4]
>>> # Pythons Counter class in also known as a bag
... from collections import Counter
>>> c1, c2 = Counter(l1), Counter(l2)
>>> # Quick calculation
... diffs = {item:(c2[item] - c1[item]) for item in set(c1) | set(c2)}
>>> diffs
{1: -1, 2: 1, 3: -1, 4: 1, 5: 0, 8: -1}
>>> # Or if you want it wordy
... for item in sorted(set(c1) | set(c2)):
...     print('Item %i changed its occurences by %2i'
...           % (item, c2[item] - c1[item]))
... 
Item 1 changed its occurences by -1
Item 2 changed its occurences by  1
Item 3 changed its occurences by -1
Item 4 changed its occurences by  1
Item 5 changed its occurences by  0
Item 8 changed its occurences by -1
>>>