果家OA, 关于数组中S[K]的最大长度,要求O(N)时间与空间

A zero-indexed array A consisting of N different integers is given. The
array contains all
integers in the range [0..N - 1]. Sets S[K] for 0 <= K < N are defined as
follows:
S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.
Sets S[K] are finite for each K.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

worst-case space complexity is O(N), beyond input
storage (not counting
the storage required for input arguments).
Elements of input arrays can be modified.

怎么做?

hashMap?

DFS应该就可以了吧，注意略过已经检查过的，应该能够满足空间和时间都是O(n)的要求

暴力枚举打tag就行了。大概是这样：while(tag[++i]==-1); c=0, j=i; while(tag[j]=-1) {tag[j]=i; j=a[j]; c++}; ret=max(ret,c)

楼主市面什么组阿?

Worst-case time complexity is O(N) 怎么做啊。。。DFS好像不行。。。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies