面试问题:从未排序的链接列表中删除重复项

Question

我正在阅读Cracking the Coding Interview,第四版:150编程面试问题和解决方案,我正在尝试解决以下问题:

2.1编写代码以从未排序的链表中删除重复项.关注:如果不允许临时缓冲区,您将如何解决此问题？

我在C#中解决它,所以我创建了自己的Node类:

public class Node<T> where T : class
{
    public Node<T> Next { get; set; }
    public T Value { get; set; }

    public Node(T value)
    {
        Next = null;
        Value = value;
    }
}

我的解决方案是遍历列表,然后为每个节点迭代通过列表的其余部分并删除任何重复项(请注意,我没有按照本书的指示实际编译或测试它):

public void RemoveDuplicates(Node<T> head)
{
    // Iterate through the list
    Node<T> iter = head;
    while(iter != null)
    {
        // Iterate to the remaining nodes in the list
        Node<T> current = iter;
        while(current!= null && current.Next != null)
        {
            if(iter.Value == current.Next.Value)
            {
                current.Next = current.Next.Next;
            }

            current = current.Next;
        }    

        iter = iter.Next;
    }
}

这是本书的解决方案(作者用java编写):

如果没有缓冲区,我们可以使用两个指针进行迭代:"current"执行正常迭代,而"runner"遍历所有先前节点以检查重复.Runner每个节点只能看到一个重复,因为如果有多个重复项,它们就已经被删除了.

public static void deleteDups2(LinkedListNode head) 
{
    if (head == null) return;

    LinkedListNode previous = head;
    LinkedListNode current = previous.next;

    while (current != null) 
    {
        LinkedListNode runner = head;

        while (runner != current) { // Check for earlier dups
            if (runner.data == current.data) 
            {
                LinkedListNode tmp = current.next; // remove current
                previous.next = tmp;
                current = tmp; // update current to next node
                break; // all other dups have already been removed
            }
            runner = runner.next;
        }
        if (runner == current) { // current not updated - update now
            previous = current;
            current = current.next;
        }
    }
}

所以我的解决方案总是寻找当前节点到最后的重复,而他们的解决方案寻找从头到当前节点的重复.我觉得这两种解决方案都会遇到性能问题,具体取决于列表中有多少重复项以及它们的分布方式(密度和位置).但总的来说:我的答案几乎和书中的答案一样好,还是更糟糕？

Answer 1

如果你给一个人一条鱼,他们会吃一天.如果你教一个人钓鱼......

我对实施质量的衡量标准是:

• 正确性:如果你在所有情况下都没有得到正确答案,那么它还没有准备好
• 可读性/可维护性:查看代码重复,可理解的名称,每个块/方法的代码行数(以及每个块执行的操作数),以及跟踪代码流的难度.如果您想了解更多相关信息,请查看任何数量的书籍,重点关注重构,编程最佳实践,编码标准等.
• 理论性能(最坏情况和最重要的): Big-O是您可以使用的指标.应该测量CPU和内存消耗
• 复杂性:估计一般的专业程序员如何实施(如果他们已经知道算法).看看这是否符合实际问题的难度

至于你的实施:

• 正确性:我建议编写单元测试来自己确定和/或从头到尾调试它(在纸上)有趣的样本/边缘情况.空,一项,两项,各种重复项等
• 可读性/可维护性:虽然你的最后两条评论没有添加任何内容,但它看起来很好.你的代码比书中的代码更明显
• 表现:我相信两者都是N平方.无论摊销成本是否较低,我都会让你弄明白:)
• 实施时间:普通专业人员应该能够在睡眠中对此算法进行编码,因此看起来很好