4

这是一个让 CS 家伙用理论大放异彩的练习。

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

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

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

编辑：所有答案都用 4 个容器解决了这个问题。是否可以只使用最初的 2？

4

5 回答 5

5

假设您有两个唯一项目列表，并且顺序无关紧要，您可以将它们都视为集合而不是列表

如果你想到一个维恩图，列表 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 个容器，它只是破坏了两个 ;-)

于 2008-09-24T13:46:33.187 回答
1

我有一段时间没有这样做了，但我相信算法是这样的......

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

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

于 2008-09-24T13:43:34.007 回答
0

乔说的。而且，如果列表太大而无法放入内存，请使用外部文件排序实用程序或合并排序。

于 2008-09-24T13:47:08.693 回答
0

缺失信息：您如何定义添加/删除？例如，如果列表（A 和 B）在服务器 A 和服务器 B 上显示相同的目录，则表示同步。如果我现在等待 10 天，再次生成列表并比较它们，我如何判断是否已删除某些内容？我不能。我只能说在服务器 B 上找不到服务器 A 上的文件和/或相反。这是因为文件已添加到服务器 A（因此在 B 上找不到文件）还是在服务器 B 上删除了文件（因此不再在 B 上找到文件）是我无法确定的文件名列表。

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

此外，我将假设没有重复项。这意味着任一列表中的每个项目在以下意义上都是独一无二的：如果我将此项目与列表中的任何其他项目进行比较（无论此比较如何进行），我总是可以说该项目小于或大于我的那个'正在比较它，但永远不会相等。例如，在处理字符串时，我可以按字典顺序比较它们，并且相同的字符串在列表中永远不会出现两次。

在这种情况下，最简单（但不一定是最佳解决方案）是：

  1. 对旧列表进行排序。例如，如果列表由字符串组成，则按字母顺序对它们进行排序。排序是必要的，因为这意味着我可以使用二进制搜索在列表中快速找到一个对象，假设它确实存在于列表中（或者快速确定它根本不存在于列表中）。如果列表未排序，则查找对象的复杂度为 O(n)（我需要查看列表中的每一项）。如果列表已排序，复杂度仅为 O(log n)，因为每次尝试匹配列表中的项目后，我总是可以排除列表中不匹配的 50% 的项目。即使列表有 100 个项目，找到一个项目（或检测该项目不在列表中）最多需要 7 次测试（或者是 8 次？反正远少于 100 次）。新列表不必排序。

  2. 现在我们执行列表消除。对于 NEW 列表中的每个项目，尝试在 OLD 列表中找到该项目（使用二进制搜索）。如果找到该项目，则将该项目从 OLD 列表中删除，并将其从 NEW 列表中删除。这也意味着列表会随着消除的进行而变得更小，因此查找将变得越来越快。由于从 a 列表中删除一个项目对列表的正确排序顺序没有影响，因此在消除阶段没有必要使用 OLD 列表。

  3. 在消除结束时，两个列表可能都是空的，在这种情况下它们是相等的。如果它们不为空，则仍在 OLD 列表中的所有项目都是 NEW 列表中缺少的项目（否则我们已将其删除），因此这些是已删除的项目。仍然在 NEW 列表中的所有项目都是不在 OLD 列表中的项目（同样，我们已经删除了它们），因此这些是添加的项目。

于 2008-09-24T14:09:40.370 回答
0

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

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

最后removedElements将包含属于list1 的元素，但不包含属于list2 的元素，并且addedElements将包含属于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)
}
于 2008-09-24T14:13:00.223 回答