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