一类由于值范围限定为正数进而有空间复杂度 O(1)的解法的算法题，如果不再限制值范围，还有没有可能空间复杂度 O(1)？
Newyorkcity · 2021-12-17 20:50:11 +08:00 · 1109 次点击这是一个创建于 1101 天前的主题，其中的信息可能已经有所发展或是发生改变。
比如返回一个单向链表中的环的首节点（如果无环返回 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
谢谢
就很想问下如果不限制值范围为正数，或者，只稍难一些，值范围是所有有效正数与零，
那还能不能获得空间复杂度 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
谢谢
 |
1
momocraft 2021-12-17 21:18:00 +08:00
为什么原地取反可以知道是否访问过
|
 |
2
geelaw 2021-12-17 21:54:39 +08:00 via iPhone
此题的标准做法是快慢指针
|
 |
3
kilasuelika 2021-12-18 00:02:49 +08:00 via Android
@momocraft 值本来是正数，访问时取反变成负数。再读的时候看它是负数，那就是访问过了。
|
 |
4
Newyorkcity OP @geelaw ？请具体一点
|
 |
5
xiaopc 2021-12-18 08:40:14 +08:00
首先这是 O(n) 的，其次牛客这道题下面的题解大部分都是快慢指针，也是 O(n) 的，具体看那些题解介绍得很清楚
|
|
6
Newyorkcity OP |
|
7
geelaw 2021-12-18 12:22:43 +08:00 via iPhone
@Newyorkcity #4 提示“快慢指针”之后就应该自己搜索了。
#6 什么叫“这类”？ 返回数组里第一次重复的索引本来就很自然地可以 O(1) 空间。 利用原来编码的冗余空间（比如这里是 32 位整数只用来表示 1 到 10000 ）的算法是比较作弊的方法，本质上还是（额外）空间 Omega(n) 的算法。 |
Select Language