这是CS人士运用该理论的一项练习。

想象一下，我们有2个带有元素的容器。文件夹，URL，文件，字符串，这真的没有关系。

什么是计算添加和删除的算法？

注意：如果有很多方法可以解决此问题，请为每个答案发布一个，以便对其进行分析和投票。

编辑：所有的答案用4个容器解决了问题。是否可以仅使用首字母2？

解决方案

我已经有一段时间没有这样做了，但我相信算法会像这样...

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

关于右列表与左列表的关系，删除包含删除的项目，添加现在包含新的项目。

假设我们有两个唯一商品列表，而排序无所谓，则可以将它们都视为集合而不是列表

如果考虑维恩图，列表A为一个圆，列表B为另一个圆，则这两个的交点就是常数池。

从A和B移除此交集中的所有元素，并且删除A中剩余的所有内容，同时添加B中剩余的所有内容。

因此，遍历A寻找B中的每个项目。如果找到它，则将其从A和B中删除

然后A是已删除的事物的列表，而B是已添加的事物的列表

我认为...

[编辑]好的，新的"仅2个容器"限制仍然适用：

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

然后，我们无需构建新列表，也不会销毁旧列表...但是，与前面的示例一样，这将花费更长的时间，我们可以遍历较短的列表并从较长的列表中删除元素。在这里，我们需要做两个列表

我会说我的第一个解决方案没有使用4个容器，它只是破坏了两个;-)

乔怎么说。并且，如果列表太大而无法容纳到内存中，请使用外部文件排序实用程序或者"合并"排序。

缺少信息：如何定义已添加/已删除？例如。如果列表(A和B)在服务器A和服务器B上显示相同的目录，则该目录是同步的。如果我现在等待10天，请再次生成列表并进行比较，如何确定是否已删除某些内容？我不能。我只能说服务器A上没有在服务器B上找到的文件和/或者反之。这是因为文件已添加到服务器A(因此在B上找不到文件)还是文件已删除在服务器B(因此在B上不再找到文件)，我无法确定文件名列表。

对于我建议的解决方案，我将假设我们有一个名为OLD的列表和一个名为NEW的列表。在OLD上找到的所有内容，但在NEW上找不到的所有内容均已删除。添加了在NEW上找到的所有内容，但未在OLD上找到的所有内容都已添加(例如，同一服务器上同一目录的内容，但是列表是在不同的日期创建的)。

此外，我将假定没有重复项。这意味着任一列表上的每个项目在以下意义上都是唯一的：如果我将此项目与列表上的任何其他项目进行比较(无论此比较的工作原理如何)，我总是可以说该项目小于或者大于我的项目正在与之比较，但绝不平等。例如。在处理字符串时，我可以按字典顺序对其进行比较，并且同一字符串在列表中永远不会出现两次。

在这种情况下，最简单的解决方案(不一定是最佳解决方案)是：

• 对OLD列表进行排序。例如。如果列表由字符串组成，请按字母顺序对它们进行排序。排序是必要的，因为这意味着我可以使用二进制搜索来快速找到列表中的对象(假设该对象确实存在)(或者快速确定它根本不在列表中)。如果列表未排序，则查找对象的复杂度为O(n)(我需要查看列表中的每个项目)。如果对列表进行排序，则复杂度仅为O(log n)，因为每次尝试匹配列表中的项目后，我总是可以排除列表中不匹配项的50％。即使列表中有100个项目，找到一个项目(或者检测到该项目不在列表中)也最多需要进行7次测试(或者是8个测试，无论如何，远远少于100)。新列表不必排序。
• 现在我们执行列表消除。对于"新"列表中的每个项目，请尝试在"旧"列表中找到该项目(使用二进制搜索)。如果找到该项目，请将其从OLD列表中删除，也将其从NEW列表中删除。这也意味着消除过程越多，列表就越小，因此查找将变得越来越快。由于从列表中删除项目对列表的正确排序顺序没有影响，因此在淘汰阶段无需使用旧列表。
• 消除结束时，两个列表可能为空，在这种情况下它们是相等的。如果它们不为空，则仍在OLD列表中的所有项目都是在NEW列表中缺少的项目(否则我们已将其删除)，因此这些都是已删除项目。仍在"新"列表中的所有项目都是未在"旧"列表中的项目(再次，我们已将其删除)，因此它们是已添加的项目。

列表中的对象是否"唯一"？在这种情况下，我将首先构建两个映射(哈希映射)，然后扫描列表并查找映射中的每个对象。

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

很抱歉将Ruby和Java混合使用：-P

最后，removeedElements将包含属于list1的元素，但不属于list2，addnedElements将包含属于list2的元素。

整个操作的成本为O(4 * N)，因为在地图/字典中的查找可能被认为是恒定的。另一方面，线性/二进制搜索列表中的每个元素将使该O(N ^ 2)。

编辑：第二个想法，将最后一个检查移到第二个循环中，我们可能会删除其中一个循环...但这很丑陋... :)

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}