草庐IT

c# - 面试题: remove duplicates from an unsorted linked list

coder 2024-03-09 原文

我正在阅读 Cracking the Coding Interview, Fourth Edition: 150 Programming Interview Questions and Solutions我正在尝试解决以下问题:

2.1 Write code to remove duplicates from an unsorted linked list. FOLLOW UP: How would you solve this problem if a temporary buffer is not allowed?

我正在用 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写的):

Without a buffer, we can iterate with two pointers: “current” does a normal iteration, while “runner” iterates through all prior nodes to check for dups. Runner will only see one dup per node, because if there were multiple duplicates they would have been removed already.

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;
        }
    }
}

所以我的解决方案总是从当前节点到末尾查找重复项，而他们的解决方案从头部到当前节点查找重复项。我觉得这两种解决方案都会遇到性能问题，具体取决于列表中有多少重复项以及它们的分布方式(密度和位置)。但总的来说:我的答案和书中的答案差不多好还是差得多？

最佳答案

如果你给一个人一条鱼，他们会吃一天。授人以渔...

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

  • 正确性:如果您没有在所有情况下都得到正确的答案，那么它还没有准备好
  • 可读性/可维护性:查看代码重复、可理解的名称、每个 block /方法的代码行数(以及每个 block 所做的事情的数量)以及跟踪的难度你的代码流。如果您想了解更多这方面的信息，请阅读许多侧重于重构、编程最佳实践、编码标准等方面的书籍。
  • 理论性能(最坏情况和摊销):Big-O是您可以使用的指标。 CPU 和内存消耗都应该测量
  • 复杂性:估计普通专业程序员需要如何实现(如果他们已经知道算法)。看看这是否符合问题的实际难度

至于您的实现:

  • 正确性:我建议编写单元测试来自行确定这一点和/或使用有趣的示例/边缘案例从头到尾调试它(在纸上)。空、一项、两项、各种重复项等
  • 可读性/可维护性:它看起来基本没问题，尽管您的最后两条评论没有添加任何内容。你的代码做了什么比书上的代码更明显一点
  • 性能:我相信两者都是 N 平方的。摊销成本是哪一个更低，我会让你弄清楚:)
  • 实现时间:普通专业人员应该能够在睡梦中编写此算法，看起来不错

关于c# - 面试题: remove duplicates from an unsorted linked list，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4542600/

c#duplicatescurrentstrongsectionjavalinked-list

有关c# - 面试题: remove duplicates from an unsorted linked list的更多相关文章

  1. c# - 如何在 ruby​​ 中调用 C# dll？ - 2

    如何在ruby​​中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL

  2. C# 到 Ruby sha1 base64 编码 - 2

    我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha

  3. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  4. Hive SQL 五大经典面试题 - 2

    目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类

  5. c# - C# 中的 Flatten Ruby 方法 - 2

    我如何做Ruby方法"Flatten"RubyMethod在C#中。此方法将锯齿状数组展平为一维数组。例如:s=[1,2,3]#=>[1,2,3]t=[4,5,6,[7,8]]#=>[4,5,6,[7,8]]a=[s,t,9,10]#=>[[1,2,3],[4,5,6,[7,8]],9,10]a.flatten#=>[1,2,3,4,5,6,7,8,9,10 最佳答案 递归解决方案:IEnumerableFlatten(IEnumerablearray){foreach(variteminarray){if(itemisIEnume

  6. ruby - 可以像在 C# 中使用#region 一样在 Ruby 中使用 begin/end 吗？ - 2

    我最近从C#转向了Ruby，我发现自己无法制作可折叠的标记代码区域。我只是想到做这种事情应该没问题:classExamplebegin#agroupofmethodsdefmethod1..enddefmethod2..endenddefmethod3..endend...但是这样做真的可以吗？method1和method2最终与method3是同一种东西吗？还是有一些我还没有见过的用于执行此操作的Ruby惯用语？ 最佳答案 正如其他人所说，这不会改变方法定义。但是，如果要标记方法组，为什么不使用Ruby语义来标记它们呢？您可以使用

  7. c# - Ruby 等效于 C# Linq 聚合方法 - 2

    什么是Linq聚合方法的ruby​​等价物。它的工作原理是这样的varfactorial=new[]{1,2,3,4,5}.Aggregate((acc,i)=>acc*i);每次将数组序列中的值传递给lambda时，变量acc都会累积。 最佳答案 这在数学以及几乎所有编程语言中通常称为折叠。它是更普遍的变形概念的一个实例。Ruby从Smalltalk中继承了这个特性的名称，它被称为inject:into:(像aCollectioninject:aStartValueinto:aBlock一样使用。)所以，在Ruby中，它称为inj

  8. c# - 先学什么？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭8年前。Improvethisquestion几年前我去学校学习编程，毕业后我找到了一份系统管理方面的工作，这就是我职业生涯的方向。我想重新开始某种开发，并且一直在“玩”C#和ASP.NET，但我已经听到很多关于其他"new"语言的讨论(新的意思是它们是新的)我)喜欢Ruby和F#。我想我想知道我是否在浪费时间学习主要的MS语言，而不是成为一名通才。很长一段时间没有离开开发社区(如果我曾经离开过的话)让我在潮流中挣扎，我不想落在时代的

  9. c# - 在 C# 中重现 Ruby OpenSSL private_encrypt 输出 - 2

    我有一个简单的Ruby脚本，我用它在某些HTTPheader上执行private_encrypt以签署要发送到ruby​​RESTAPI的Web请求，该API会根据Base64编码字符串测试Base64编码字符串生成而不是解码Base64和解密数据然后测试原始字符串。我使用的脚本是require"openssl"require"base64"path_to_cert=ARGV[0].dupplain_text=Base64.decode64(ARGV[1].dup)private_key=OpenSSL::PKey::RSA.new(File.read(path_to_cert))pu

  10. C# 的 LINQ 用于在 ruby​​ 中等效的集合操作 - 2

    我是ruby​​开发的新手，我目前正在使用rails2.3.11在ruby​​1.8.7中开发一个项目，我想知道这种语言是否有与C#的linq等效的集合操作，例如where子句。谢谢。 最佳答案 Ruby中Linq的where等价于find_all检查documentationfortheEnumerableModule用于其他功能。 关于C#的LINQ用于在ruby​​中等效的集合操作，我们在StackOverflow上找到一个类似的问题： https://

随机推荐