编写函数 RemoveDuplication() 的最有效实现

Question

所以我正在研究，我有这个问题，编写函数 RemoveDuplication() 的最有效实现，它删除列表中的任何重复项。假设列表已排序但可能有重复。因此，如果列表最初是 <2, 2, 5, 6, 6, 6, 9>，您的函数应该使其成为 <2, 5, 6, 9>。

我想到的删除重复的代码就在这里，我想知道是否有更有效的方法来删除列表中的重复

template <class T>
void DLList<T>:: RemoveDuplication()
{
    for(DLLNode<T>*ptr = head; ptr!=NULL; ptr=ptr->next)
        while (ptr->val == ptr->next->val)
        {
            ptr->next->next->prev = ptr;
            ptr->next = ptr->next->next;
        }
}

Answer 1

看起来你的代码会运行在 O(n) 中，这对算法很有用。它可能不会更有效率，因为您必须访问每个项目才能删除它。

如果您不想删除重复的对象，但想return一个包含非重复对象的新列表，您可以稍微修改一下通过使其 O(m) 更快，其中 m 是唯一数字的数量，它小于或等于 n。但是我想不出任何办法来做到这一点。

Recapping，可以稍微快点，但这很难，改进可以忽略不计。

ps。当您从列表中删除内容时，别忘了将其删除 ;)

Answer 2

我觉得O(n)还可以。然而最重要的是你的程序会崩溃:-)

for(DLLNode<T>*ptr = head; ptr!=NULL; ptr=ptr->next)
    while (ptr->val == ptr->next->val)

代码正在引用 ptr->next，但没有检查它是否是 != NULL。因此，算法在到达列表的最后一个元素时应该会崩溃。

现在给你一个优化问题：如何在每次迭代时不测试 ptr 和 ptr->next 的情况下使程序正确？

编写函数 RemoveDuplication() 的最有效实现

Write the most efficient implementation of the function RemoveDuplication()

c++

performance

memory-efficient