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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1072 天前的主题，其中的信息可能已经有所发展或是发生改变。

比如返回一个单向链表中的环的首节点（如果无环返回 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

2021-12-17 21:18:00 +08:00

为什么原地取反可以知道是否访问过

geelaw

2021-12-17 21:54:39 +08:00 via iPhone

此题的标准做法是快慢指针

kilasuelika

2021-12-18 00:02:49 +08:00 via Android

@momocraft 值本来是正数，访问时取反变成负数。再读的时候看它是负数，那就是访问过了。

Newyorkcity

2021-12-18 08:11:23 +08:00

@geelaw ？请具体一点

xiaopc

2021-12-18 08:40:14 +08:00

首先这是 O(n) 的，其次牛客这道题下面的题解大部分都是快慢指针，也是 O(n) 的，具体看那些题解介绍得很清楚

Newyorkcity

2021-12-18 09:47:10 +08:00

@geelaw
@xiaopc

那除了这道题可以快慢指针外，这类题都可以吗。。比如返回数组中第一次重复的值的索引

geelaw

2021-12-18 12:22:43 +08:00 via iPhone

@Newyorkcity #4 提示“快慢指针”之后就应该自己搜索了。

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

利用原来编码的冗余空间（比如这里是 32 位整数只用来表示 1 到 10000 ）的算法是比较作弊的方法，本质上还是（额外）空间 Omega(n) 的算法。