当前在线人数12554
首页 - 分类讨论区 - 海外生活 - 待字闺中版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:果家OA, 关于数组中S[K]的最大长度,要求O(N)时间与空间
[同主题阅读] [版面: 待字闺中] [作者:restful] , 2017年04月14日17:37:56
restful
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: restful (service), 信区: JobHunting
标  题: 果家OA, 关于数组中S[K]的最大长度,要求O(N)时间与空间
发信站: BBS 未名空间站 (Fri Apr 14 17:37:56 2017, 美东)

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.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers, returns the size of the
largest set S[K]
for this array. The function should return 0 if the array is empty.
For example, given array A such that:  A[0] = 5, A[1] = 4, A[2] = 0, A[3] =
3, A[4] = 1, A[5] = 6, A[6] = 2
the function should return 4, because set S[2] equals { 0, 5, 6, 2 } and has
four elements.
No other set S[K] has more than four elements.
Assume that:
·         N is an integer within the range [0..1,000,000];
·         the elements of A are all distinct;
·         each element of array A is an integer within the range [0..N-1].
Complexity:
·         expected worst-case time complexity is O(N);
·         expected 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.

怎么做?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 67.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996