algorithm - 之前和之后的集合中发生了什么变化

Question

这是一个面试问题：给你两个数组：之前：{3, 3, 5, 8, 1} 和之后：{5, 3, 2, 4}。确定从“之前”数组中删除/添加了哪些数字以获得“之后”。

我可以考虑为每个列表使用两个哈希图，并比较它们以判断每个元素是否已添加或删除。

有人可以为此想出更好的方法或提供替代解决方案（具有更好的时间/空间复杂性）吗？

Answer 1

您可以将每个列表存储在袋子中，然后找到袋子中每种项目类型的发生率变化。

这是一些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
>>>  

Answer 2

在上述线程之一中讨论的解决方案将是 O(n+m) n,m 是 2 个数组的大小，因为在最坏的情况下您需要遍历两个数组的整个长度。一个可能的改进是对第一个数组中的第二个数组中的每个元素执行二进制搜索，如果找到，则将其从第一个数组中删除。如果不将其添加到数组中。所有迭代后，将剩余元素添加到第一个数组到最终数组列表。时间复杂度为 O(mlogn)

function binaryIndexOf(searchElement, searchArray) {
'use strict';
var minIndex = 0;
var maxIndex = searchArray.length - 1;
var currentIndex;
var currentElement;

while (minIndex <= maxIndex) {
    currentIndex = (minIndex + maxIndex) / 2 | 0;
    currentElement = searchArray[currentIndex];

    if (currentElement < searchElement) {
        minIndex = currentIndex + 1;
    }
    else if (currentElement > searchElement) {
        maxIndex = currentIndex - 1;
    }
    else {
        return currentIndex;
    }
}

return -1;
}
var before = [3, 3, 5, 8, 1];
var after = [5, 3, 2, 4];
var intsort = function (a, b) {
return a - b
};
var i;
var resultArray = [];
var elementIndex;
before.sort(intsort);
after.sort(intsort); 
for (i = 0; i < after.length; i++) {
 elementIndex = binaryIndexOf(after[i], before);
 if (elementIndex != -1)
        before.splice(elementIndex, 1);
 else
        resultArray.push(after[i]);
 }
j = 0;
while (j < before.length) { 
  resultArray.push(before[j++]); 
}
console.log("result=" + resultArray);

Answer 3

我认为您建议的答案（使用两个哈希图）是最好的结果，即 O(n+m)，因为您总是需要至少访问每个数组的每个元素一次。

这是我的 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 来保持简洁；用循环和 HashSet 中的等效项重写可能会更有效。