如何从链表中删除重复的奇数？

Question

要求/约束​​：

1. 仅删除重复项
2. 保留一个副本
3. 列表最初未排序

这如何在 C 中实现？ （算法和/或代码将不胜感激！）

Answer 1

如果列表很长并且您想要合理的性能并且可以分配额外的 log(n) 内存，则可以使用 qsort 或合并排序对 nlog(n) 进行排序：

http://swiss-knife.blogspot.com/2010/11/sorting.html

然后你可以删除重复项n （总数为：nlog(n) + n）

如果你的列表非常小，你可以像 jswolf19 建议的那样做，你会得到：n(n-1)/2 最差。

Answer 2

有几种不同的方法可以检测/删除重复项：

嵌套循环

按顺序获取下一个值，然后扫描直到列表末尾以查看该值是否再次出现。这是 O(n²) ——尽管我相信界限可以更低？ -- 但实际性能可能会更好，因为仅从 i 扫描到 end （而不是从 0 到 end）已完成，并且可能会提前终止。除了一些变量之外，这不需要额外的数据。

（参见 Christoph 的回答，了解如何仅使用链表的遍历和破坏性的“附加”到新列表来完成此操作 - 例如，嵌套循环不必“感觉”像嵌套循环。）

和过滤

排序 列表（可以修改合并排序以在链接列表上工作），然后检测重复值（它们现在将并排）。如果排序良好，时间复杂度为 O(n*lg(n))。排序阶段通常是/可能是破坏性的（例如，您有“一份副本”），但它已被修改；-)

扫描并维护查找

扫描列表，并在扫描列表时将值添加到查找中。如果查找已包含所述值，则存在重复项！如果查找访问的时间复杂度为 O(1)，则此方法的复杂度可以为 O(n)。通常，“散列/字典”或“集合”用作查找，但如果仅使用有限范围的积分，则数组将正常工作（例如索引就是值）。这需要额外的存储空间，但不需要“额外的副本”——至少在字面上是这样。

对于较小的 n 值，大 O 几乎毫无价值;-)

快乐编码。

Answer 3

我要么对

• 列表进行合并排序，然后进行线性扫描以删除重复项，
• 使用基于插入排序的算法，该算法在重新构建列表时已经删除了重复项。

前者会更快，后者更容易从头开始实现：只需构造一个新列表的方法是从旧列表中弹出元素，然后通过扫描将它们插入到新列表中，直到找到具有更大值的元素（在这种情况下，您将该元素插入到列表中）或相等的值（在这种情况下，您将丢弃该元素）元素）。

Answer 4

那么，您可以先对列表进行排序，然后检查是否有重复项，或者您可以执行以下操作之一：

for i from 0 to list.length-1
    for j from i+1 to list.length-1
        if list[i] == list[j]
            //delete one of them
        fi
    loop
loop

Answer 5

这可能是最未经优化的废话，但它可能会起作用。

遍历列表，每次转到下一个对象时都持有指向前一个对象的指针。在迭代循环中遍历所有内容以检查是否有重复项。如果存在重复项，现在返回主迭代循环，获取下一个对象。将前一个对象指向下一个对象的指针设置为刚刚检索到的对象，然后跳出循环并重新启动整个过程，直到没有重复项为止。

Answer 6

您可以使用哈希表在线性时间内完成此操作。

您需要按顺序浏览列表。每次遇到奇数元素时，请在哈希表中查找它。如果该数字已在哈希表中，则将其从列表中删除，如果没有，则将其添加到哈希表中并继续。

基本上，这个想法是，对于您在列表中扫描的每个元素，您可以在恒定的时间内检查它是否是您所看到的前一个元素的重复项。这仅需要一次遍历列表，并且在最坏的情况下会占用线性量的内存（最坏的情况是列表中的每个元素都是唯一的奇数，因此哈希表与列表一样长）。