V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Newyorkcity
V2EX  ›  问与答

一类由于值范围限定为正数进而有空间复杂度 O(1)的解法的算法题,如果不再限制值范围,还有没有可能空间复杂度 O(1)?

  •  
  •   Newyorkcity · 2021-12-17 20:50:11 +08:00 · 998 次点击
    这是一个创建于 831 天前的主题,其中的信息可能已经有所发展或是发生改变。
    比如返回一个单向链表中的环的首节点(如果无环返回 null )的算法题 如果节点的值的范围限定为正数 则可以原地取反的方式来判断该节点是不是已经访问过从而解题

    就很想问下如果不限制值范围为正数,或者,只稍难一些,值范围是所有有效正数与零,

    那还能不能获得空间复杂度 O(1)的解法呀?

    https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

    谢谢
    7 条回复    2021-12-18 12:22:43 +08:00
    momocraft
        1
    momocraft  
       2021-12-17 21:18:00 +08:00
    为什么原地取反可以知道是否访问过
    geelaw
        2
    geelaw  
       2021-12-17 21:54:39 +08:00 via iPhone
    此题的标准做法是快慢指针
    kilasuelika
        3
    kilasuelika  
       2021-12-18 00:02:49 +08:00 via Android
    @momocraft 值本来是正数,访问时取反变成负数。再读的时候看它是负数,那就是访问过了。
    Newyorkcity
        4
    Newyorkcity  
    OP
       2021-12-18 08:11:23 +08:00
    @geelaw ?请具体一点
    xiaopc
        5
    xiaopc  
       2021-12-18 08:40:14 +08:00
    首先这是 O(n) 的,其次牛客这道题下面的题解大部分都是快慢指针,也是 O(n) 的,具体看那些题解介绍得很清楚
    Newyorkcity
        6
    Newyorkcity  
    OP
       2021-12-18 09:47:10 +08:00
    @geelaw
    @xiaopc

    那除了这道题可以快慢指针外,这类题都可以吗。。比如返回数组中第一次重复的值的索引
    geelaw
        7
    geelaw  
       2021-12-18 12:22:43 +08:00 via iPhone
    @Newyorkcity #4 提示“快慢指针”之后就应该自己搜索了。

    #6 什么叫“这类”?
    返回数组里第一次重复的索引本来就很自然地可以 O(1) 空间。

    利用原来编码的冗余空间(比如这里是 32 位整数只用来表示 1 到 10000 )的算法是比较作弊的方法,本质上还是(额外)空间 Omega(n) 的算法。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3845 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 10:32 · PVG 18:32 · LAX 03:32 · JFK 06:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.